資料結構基礎加強之排序算法
冒泡排序-Bubble Sort
思想：做升序排列，通過相鄰兩數之間兩兩交換，讓大的數先冒出來，到數組的尾部，小的數後冒出來。
圖例：
排序之前：
第一次循環後：
代碼實作：
public class BubbleSort {
public static void main(String[] args) {
int[] array = { , , , , , , , , };
solution(array);
}
// 冒泡排序升序排列
private static void solution(int[] array) {
for (int i = ; i < array.length - ; i++) {
for (int j = ; j < array.length - ; j++) {
if (array[j] > array[j + ]) { // 相鄰2個數比較如果前值大于後值則交換
swap(array, j + , j);
}
}
}
for (int i : array) {
System.out.print(i + " ");
}
}
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
插入排序 -Insert Sort
思想：每次将一個記錄插入到已經排好序的有序表中，進而得到新的有序表。
将序列的第一個記錄看成有序的子序列，從第二個記錄開始逐個進行插入，直到整個序列有序。
圖例：
排序之前：
第一次排序後：
因為數組第二個位置和第一個位置之間是有序的是以不變化。
第三次排序後：
第三個數和第二個交換，使前三個數有序。
代碼實作：
public class InsertSort {
public static void main(String[] args) {
int[] array = { , , , , , , , , };
solution(array);
}
// 插入排序升序排列
private static void solution(int[] array) {
for (int i = ; i < array.length; i++) {
int cur = array[i];
int j = i - ;
while (j >= ) {
int k = j;
if (array[j] < cur) {
break;
} else {
array[++k] = array[j];
}
j--;
}
array[++j] = cur;
}
for (int i : array) {
System.out.print(i + " ");
}
}
}
選擇排序 -Select Sort
思想：每次找一個最小值。放到數組的起始位置。
即從起始位置，每次循環選擇未排序的第一個值作為哨兵，依次與後面的值比較，如果哨兵小，則兩兩交換，直至數組最後一個位置，此時哨兵位置的數為最小值。
圖例：
排序之前：
第一次排序之後：
數組最後一個位置的值比第一個位置的小，兩兩交換，數組最小值放到第一個位置。
代碼實作：
public class SelectSort {
public static void main(String[] args) {
int[] array = { , , , , , , , , };
solution(array);
}
// 選擇排序升序排列
private static void solution(int[] array) {
for (int i = ; i < array.length; i++) {
for (int j = i + ; j < array.length; j++) {
if (array[i] > array[j]) {
swap(array, i, j);
}
}
}
for (int i : array) {
System.out.print(i + " ");
}
}
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
希爾排序 -Shell Sort
思想：對直接插入排序的改進，選擇一個增量序列{size/2,t1,…..,1}。
根據對應的增量ti，将待排序列分割成若幹長度為m 的子序列，分别對各子表進行直接插入排序，依次減小增量，當增量因子為1時，整個序列作為一個表處理。
圖例：
排序前：
第一次排序之後：因為數組長為9，是以初始增量為4
代碼實作：
public class ShellSort {
public static void main(String[] args) {
int[] array = { , , , , , , , , };
solution(array);
}
// 希爾排序實作升序排列
private static void solution(int[] array) {
int size = array.length;
for (int i = size / ; i >= ; i--) {
for (int j = ; j < array.length; j++) {
if ((j + i) < array.length) {
if (array[j] > array[j + i]) {
swap(array, j, j + i);
}
}
}
}
for (int i : array) {
System.out.print(i + " ");
}
}
// 數組2個元素的交換
private static void swap(int[] array, int j, int i) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
歸并排序 -Merge Sort
思想：使用分治法解決問題，每一次将數組對分，依次遞歸，直至每個數組隻有一個元素，此時數組是有序的，然後将分開的數組，相鄰兩兩之間合并，直至最後得到有序的數組。
圖例：
代碼實作：
public class MergeSort {
public static void main(String[] args) {
int[] array = { , , , , , , , , };
int i = ;
int j = array.length - ;
solution(array, i, j);
for (int e : array) {
System.out.print(e + " ");
}
}
private static void solution(int[] array, int left, int right) {
int mid = (right + left) / ;
if (left < right) {
solution(array, left, mid); // 左邊
solution(array, mid + , right); // 右邊
merge(array, left, mid, right);// 歸并
}
}
// 歸并實作升序排列
private static void merge(int[] array, int left, int mid, int right) {
int[] temp = new int[right - left + ];
int i = left;
int j = mid + ;
int k = ; // temp數組索引
while (i <= mid && j <= right) { // 填入2數組中較小的值
if (array[i] < array[j]) {
temp[k] = array[i];
k++;
i++;
} else {
temp[k] = array[j];
k++;
j++;
}
}
// 左邊數組剩餘填入
while (i <= mid) {
temp[k++] = array[i++];
}
// 右邊數組剩餘填入
while (j <= right) {
temp[k++] = array[j++];
}
for (int index = ; index < temp.length; index++) {
array[index + left] = temp[index];
}
}
}
快速排序 -Quick Sort
思想：采用分治法，每次找一個基準值，對數組處理，讓小于基準值的位于基準值的左邊，大于基準值的位于基準值的右邊。然後對左右兩邊做遞歸處理。
圖例：每次取第一個值為基準值
排序之前：
第一次排序之後：
代碼實作：
public class QuickSort {
public static void main(String[] args) {
int[] array = { , , , , , , , , };
int low = ;
int high = array.length - ;
solution(array, low, high);
for (int i : array) {
System.out.print(i + " ");
}
}
// 遞歸實作升序快速排序
private static void solution(int[] array, int low, int high) {
if (low < high) {
int i = low;
int j = high;
int curr = array[i];
while (i < j) {
while (curr <= array[j] && i < j) {
j--;
}
if (i < j) {
array[i] = array[j];
i++;
}
while (curr >= array[i] && i < j) {
i++;
}
if (i < j) {
array[j] = array[i];
j--;
}
}
array[i] = curr;
solution(array, low, i - );
solution(array, i + , high);
}
}
}
基數排序-Radix Sort
思想：桶排序的一種。讓個位、十位、百位的大小依次對數組進行排序。
圖例：
代碼實作：
public class RadixSort {
public static void main(String[] args) {
int[] array = { , , , , , , , , };
solution(array);
for (int i : array) {
System.out.print(i + " ");
}
}
private static void solution(int[] array) {
int maxPos = getMaxPos(array);
int[][] temp = new int[][array.length + ]; // 臨時數組 按元素位 上的數值大小 依次存儲元素
for (int i = ; i < temp.length; i++) {
temp[i][] = ; // 記錄行内元素的個數 初始化為0
}
for (int pos = ; pos < maxPos; pos++) {
for (int index = ; index < array.length; index++) {
int row = getPos(array[index], pos);
int col = ++temp[row][];
temp[row][col] = array[index];
}
// 收集元素
for (int row = , i = ; row < ; row++) {
for (int col = ; col <= temp[row][]; col++) {
array[i++] = temp[row][col];
}
temp[row][] = ; // 恢複行元素數記錄 下次繼續使用
}
}
}
// 取出數組元素在目前Pos上的數 pos = 1:個位 pos = 2:十位...
private static int getPos(int cur, int pos) {
int temp = ;
for (int i = ; i < pos - ; i++) {
temp = temp * ;
}
return (cur / temp) % ;
}
// 得到數組中最大元素的位數
private static int getMaxPos(int[] array) {
int max = array[];
for (int i = ; i < array.length; i++) {
if (max < array[i]) {
max = array[i];
}
}
int result = ;
int temp = ;
while (true) {
temp = temp * ;
if (max / temp != ) {
result++;
} else {
break;
}
}
return result;
}
}
堆排序 -Heap Sort
基本思想：基于最小堆或者最大堆。對給定的數組建立堆，依據堆對數組排序
具體說明可以參考：http://blog.csdn.net/a815060271/article/details/72328745
各個排序算法之間的比較
各排序算法穩定性，時間複雜度，空間複雜度分析：
具體代碼可以參考：https://github.com/Li-JY/algorithm-and-datastructure/tree/master/src/sort