八大排序（尚未完善）

基本的流程就不写了，不会就自己看代码，按照代码跑6、7遍就懂了

java的数组值交换

异或交换运算（需要保证位置不同）：

public static void swap(int[] arr, int i, int j){arr[i] = arr[i] ^ arr[j];arr[j] = arr[i] ^ arr[j];arr[i] = arr[i] ^ arr[j];      
}

1. 冒泡排序

时间复杂度O(N^2)，额外空间复杂度O(1)

public static void bubbleSort(int[] arr){if(arr == null || arr.length < 2)return;for(int e = arr.length - 1; e > 0; e--)for(int i = 0; i < e; i++){if(arr[i] > arr[i + 1])swap(arr, i, i + 1);}}}

2. 插入排序

时间复杂度O(N^2)，额外空间复杂度O(1)

public static void insertionSort(int[] arr){if(arr == null || arr.length < 2)return;for(int i = 1; i < arr.length; i ++){for(int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--){swap(arr, j, j + 1);}}}

3. 选择排序

// 选择排序public static void selectSort(int[] arr){if(arr == null || arr.length < 2)return;for(int i = 0; i < arr.length; i ++){int minIndex = i;for(int j = i; j < arr.length; j ++){minIndex = arr[minIndex] < arr[j]? minIndex : j;}if(i == minIndex)continue;swap(arr, i, minIndex);}return;}

4. 基数排序

// 基数排序 daixiepublic static void radixSort(int[] arr){if(arr == null || arr.length < 2)return;radixSort(arr, 0, arr.length - 1, maxbits(arr));}public static int maxbits(int[] arr){int max = Integer.MIN_VALUE;for(int i = 0; i < arr.length; i++){max = Math.max(max, arr[i]);}int res = 0;while(max != 0){res ++;max /= 10;}return res;}public static void radixSort(int[] arr, int L, int R, int digit){final int radix = 10;int i = 0,j = 0;// 有多少个数准备多少个辅助空间int[] bucket = new int[R - L + 1];for(int d = 1; d <= digit; d++){int[] count = new int[radix];for(i = L; i <= R; i++){j = getDigit(arr[i], d);count[j]++;}for(i =1; i < radix; i++){count[i] = count[i] + count[i - 1];}for(i = R; i >= L; i--){j = getDigit(arr[i], d);bucket[count[j] - 1] = arr[i];count[j]--;}for( i = L, j = 0; i <= R; i++, j++){arr[i] = bucket[j];}}}// 取数值public static int getDigit(int x, int d){return ((x / ((int)Math.pow(10, d - 1))) % 10);}

5. 希尔排序

// 希尔排序public static void shellSort2(int[] arr, int gap){for(int i = gap; i < arr.length; i ++){for(int j =i - gap;j >= 0; j -= gap){if(arr[j] > arr[j + gap])swap(arr, j, j + gap);}}return;}// 部分public static void shellSort(int[] arr){if(arr == null || arr.length < 2){return;}int[] gap = new int[arr.length / 2 + 1];int num = 0;int len = arr.length;while(len > 1){gap[num++] = len / 2;len /= 2;}System.out.println(Arrays.toString(gap));System.out.println(num);for(int i =0; i < num; i++)shellSort2(arr, gap[i]);}

6. 快速排序

public static void quickSort(int[] arr){if(arr == null || arr.length < 2){return;}quickSort(arr, 0, arr.length - 1);}public static void quickSort(int[] arr, int L, int R){if(L < R){swap(arr, L + (int)(Math.random() * (R - L + 1)), R);int[] p = partition(arr, L, R);quickSort(arr, L, p[0] - 1);quickSort(arr, p[1] + 1, R);}}

7. 归并排序

待写

8. 堆排序

// heapInsertpublic static void heapInsert(int[] arr, int index){while(arr[index] > arr[(index - 1) / 2]){swap(arr, index, (index - 1) / 2);index = (index - 1) / 2;}}// 某个数在index的位置，能否往下移动public static void heapify(int[] arr, int index, int heapSize){int left = index * 2 + 1;while(left < heapSize){// 两个孩子中，谁值大，下标给largestint largest = left + 1 < heapSize && arr[left + 1] > arr[left]? left + 1 : left;// 父和较大孩子比较largest = arr[largest] > arr[index] ? largest : index;if(largest == index){break;}swap(arr, largest, index);index = largest;left = index * 2 + 1;}}// 堆排序public static void heapSort(int[] arr){if(arr == null || arr.length < 2){return;}// 构造大根堆for(int i = 0; i < arr.length; i++)heapInsert(arr, i);int heapSize = arr.length;swap(arr, 0, --heapSize);while(heapSize > 0){heapify(arr, 0, heapSize);swap(arr, 0, --heapSize);}}