Java 排序

排序

1. 稳定的排序：排序之前和排序之后它们俩的相对顺序没有发生变化
2. 内部排序：在内存上的排序
3. 外部排序：需要借助磁盘等外部空间进行的排序

插入排序

1. 思想：假设这组数据的第一个元素是有序的，从第二个元素和前面的元素进行比较，找到合适的位置进行插入

// 插入排序public static void insertSort(int[] array){for(int i = 1;i < array.length;i++){int j = i - 1;int tmp = array[i];for(;j >= 0;j--){if(array[j] > tmp){array[j+1] = array[j];}else{break;}}array[j + 1] = tmp;}}

分析

1. 时间复杂度：O(N^2)
   最坏情况：O(N^2)
   最好情况：有序的数组，O(N)
   数据越有序，排序越快
   适用于待排序数组基本上趋于有序了，时间复杂度趋于O(N)
2. 空间复杂度：O(1)
3. 稳定性：是一个稳定的排序
   例子：5 5 7
   稳定的排序可以改成不稳定的排序，但是不稳定的排序不能改成稳定的排序

希尔排序

1. 对直接插入排序进行了优化，如果是 5 4 3 2 1 会退化为O(N^2)
2. 分组：分完组后，每组都采用直接插入排序
3. 中间隔一些元素进行分组的好处：比较大的元素都往后走了，比较小的元素都往前走了
4. 缩小增量到最后会把整体看成是一组，5 3 1 组，前面的5 3 都是预排序，真正的排序是最后的一组
5. 缩小增量的目的：为了让排序更接近O(N)，为了让排序更快

// 希尔排序public static void shellSort(int[] array){int gap = array.length;while(gap > 1){gap /= 2;shell(array,gap);}}// 对每组进行插入排序public static void shell(int[] array,int gap){for(int i = gap;i < array.length;i++){int j = i - gap;int tmp = array[i];for(;j >= 0;j -= gap){if(array[j] > tmp){array[j+gap] = array[j];}else{break;}}array[j + gap] = tmp;}}

分析

1. 时间复杂度：O(N^1.3 - N ^ 1.5)，时间复杂度不好计算
2. 空间复杂度：O(1)
3. 稳定性：不稳定的排序

检测排序速度：

public static void testInsert(int[] array){long startTime = System.currentTimeMillis();int[] tmp = Arrays.copyOf(array,array.length);Sort.insertSort(tmp);long endTime = System.currentTimeMillis();System.out.println(" " + (endTime - startTime));}public static void testShell(int[] array){long startTime = System.currentTimeMillis();int[] tmp = Arrays.copyOf(array,array.length);Sort.shellSort(tmp);long endTime = System.currentTimeMillis();System.out.println(" " + (endTime - startTime));}// 逆序初始化public static void initOrder(int[] array){for(int i = 0;i < array.length;i++){array[i] = array.length - i;}}public static void main(String[] args) {int[] arr = new int[10000];initOrder(arr);testInsert(arr);testShell(arr);}

选择排序

1. 在当前i下标对应的值的后面，找到后面最小的值和i下标对应的值交换
   

	// 交换public static void swap(int i, int j, int[] array){int tmp = array[i];array[i] = array[j];array[j] = tmp;}// 选择排序public static void selectSort(int[] array){// 在i下标的后面找到比i下标对应的值的最小值,然后交换int n = array.length;for(int i = 0;i < n;i++){int minIndex = i;for(int j = i + 1;j < n;j++){if(array[j] < array[i]){if(array[j] < array[minIndex]){minIndex = j;}}}swap(i,minIndex,array);}}

2. 双向选择排序
   时间复杂度还是O(N^2)
   左边找最大的，右边找最小的，和第一个数和最后一个数交换
   
   存在缺陷，maxIndex下标可能是在0下标是最大的，0下标会和最小值小标的值交换，那么0下标就不是最大值下标，应该更新为maxIndex = minIndex

public static void selectSort2(int[] array){// 在i下标的后面找到比i下标对应的值的最小值,然后交换int left = 0;int right = array.length - 1;while(left < right){int minIndex = left;int maxIndex = left;for(int i = left + 1;i <= right;i++){if(array[i] < array[minIndex]){minIndex = i;}if(array[i] > array[maxIndex]){maxIndex = i;}}swap(left,minIndex,array);// 第一个数是最大的数,防止最小的下标和第一个数换了,最大值就在minIndex的位置了if(maxIndex == left){maxIndex = minIndex;}swap(right,maxIndex,array);left++;right--;}}

分析

1. 时间复杂度：O(N^2)
2. 空间复杂度：O(1)
3. 稳定性：不稳定的排序

堆排序

// 堆排序private static void shifDown(int[] array,int parent,int len){int child = 2 * parent + 1;while(child < len){if(child + 1 < len && array[child] < array[child + 1]){child++;}if(array[child] > array[parent]){swap(child,parent,array);parent = child;child = 2 * parent + 1;}else{break;}}}private static void createHeap(int[] array){// 建立大根堆for(int parent = (array.length - 1 - 1) / 2;parent >= 0;parent--) {shifDown(array, parent, array.length);}}public static void heapSort(int[] array){createHeap(array);int end = array.length - 1;while(end > 0){swap(end,0,array);shifDown(array,0,end);end--;}}

分析

1. 时间复杂度：O(N * logN)
2. 空间复杂度：O(1)
3. 稳定性：不稳定的排序

冒泡排序

// 冒泡排序public static void bubbleSort(int[] array){// i是趟数for(int i = 0;i < array.length;i++){// j是比较的大小的boolean flag = true;for(int j = 0;j < array.length - i - 1;j++){if(array[j] > array[j + 1]){swap(j,j + 1,array);flag = false;}}if(flag) {break;}}}

分析

1. 时间复杂度：O(N ^ 2)
2. 空间复杂度：O(1)
3. 稳定性：稳定的排序

快速排序

霍尔法

1. 根据二叉树进行递归划分

// 快速排序public static void quickSort(int[] array){quick(array,0,array.length - 1);}private static void quick(int[] array,int start,int end){if(start >= end){return;}int prvot = partitionHoare(array,start,end);quick(array,start,prvot - 1);quick(array,prvot + 1,end);}private static int partitionHoare(int[] array,int left,int right){// 基准元素int tmp = array[left];// 记录第一个基准下标int i = left;while(left < right) {// 必须先找先右再左// 找小while (left < right && array[right] >= tmp) {right--;}// 找大while (left < right && array[left] <= tmp) {left++;}swap(left, right, array);}swap(i,left,array);return left;}

2. 为什么有等于号？
   没有等于号，会死循环，比如两端都是6

4. 为什么先从右边开始，不先从左边开始？
   先走左边的话，先遇到大的停下来，如果相遇的话，那么相遇位置的值就是大于基准元素的，这时候交换的话，6的左边有一个数比6大
   

分析

1. 时间复杂度：
   最好情况下：O(N * logN)
   每层都有N个节点，高度为logN，需要每个节点都遍历到，N * logN次遍历
   最坏情况下：O(N^2)，有序/逆序，单分支的树
2. 空间复杂度：
   最好情况下：O(logN)
   最坏情况下：O(N)，有序/逆序，单分支的树
   递归左边再递归右边，递归右边左边没有释放
3. 稳定性：不稳定的排序

挖坑法找基准

1. 先走右边再走左边，以第一个元素为基准，并且拿出基准元素，基准元素的位置就是坑，如果右边找到比基准小的，把它放入坑中，左边找到比基准元素大的放到坑中，最后两者相遇，把基准元素放入其中

// 挖坑法private static int partitionHole(int[] array,int left,int right){// 基准元素int tmp = array[left];while(left < right) {// 必须先找先右再左// 找小while (left < right && array[right] >= tmp) {right--;}array[left] = array[right];// 找大while (left < right && array[left] <= tmp) {left++;}array[right] = array[left];}array[left] = tmp;return left;}

前后指针法

1. 如果cur比基准元素小并且cur下标的值和prev下标的值不相等，

// 前后指针法public static int partition(int[] array,int left,int right){int prev = left;int cur = left + 1;while(cur <= right){while(array[cur] < array[left] && array[++prev] != array[cur]){swap(cur,prev,array);}cur++;}swap(prev,left,array);return prev;}

题目

1. 优先试挖坑法，其次是Hoare，最后是前后指针法

A

快排的优化

1. 均匀的分割数组
2. 让递归的次数变少

三数取中法

1. 三数取中法：left，right，mid三个下标中的中间值和第一个数交换位置，然后右边找比基准元素小的值，左边找比基准元素大的值
2. 规定array[mid] <= array[left] <= array[right]
   

// 三数取中法,求中位数的下标private static int middleNum(int[] array,int left,int right){int mid = (left + right) / 2;if(array[left] < array[right]){// 1. x < 3 < 9// 2. 3 < 9 < x// 3. 3 < x < 9if(array[mid] < array[left]){return left;}else if(array[mid] > array[right]){return right;}else{return mid;}}else{// 9 > 3 == left > right// 1. x > left > rightif(array[mid] > array[left]){return left;}else if(array[right] > array[mid]){// 2. left > right > xreturn right;}else{// 3. left > x > rightreturn mid;}}}private static void quick(int[] array,int start,int end){if(start >= end){return;}// 1 2 3 4 5 6 7// 中间值的下标和第一个数交换,作为新的基准元素int index = middleNum(array,start,end);swap(index,start,array);// 4 2 3 1 5 6 7// 为了让左右分布更均匀,降低树的高度,减少递归的次数int prvot = partition(array,start,end);quick(array,start,prvot - 1);quick(array,prvot + 1,end);}

只剩最后几层时，使用插入排序进行优化，降低递归次数，可以使用插入排序是因为前面递归成有序的序列了

public static void insertSort(int[] array,int left,int right){for(int i = left + 1;i <= right;i++){int j = i - 1;int tmp = array[i];for(;j >= left;j--){if(array[j] > tmp){array[j+1] = array[j];}else{break;}}array[j + 1] = tmp;}}private static void quick(int[] array,int start,int end){if(start >= end){return;}if(end - start + 1 <= 15){// 减少递归的次数// 因为最后几层节点数最多,递归次数也多insertSort(array,start,end);return;}// 1 2 3 4 5 6 7// 中间值的下标和第一个数交换,作为新的基准元素int index = middleNum(array,start,end);swap(index,start,array);// 4 2 3 1 5 6 7// 为了让左右分布更均匀,降低树的高度,减少递归的次数int prvot = partition(array,start,end);quick(array,start,prvot - 1);quick(array,prvot + 1,end);}

非递归实现快排

1. 找基准里面会进行交换元素，进行排序，外面就进行找到左右下标位置

 // 非递归实现快速排序public static void quickSortNor(int[] array){int start = 0;int end = array.length - 1;Stack<Integer> stack = new Stack<>();int pivot = partitionHoare(array,start,end);if(pivot - 1 > start){// 左边有两个元素stack.push(start);stack.push(pivot - 1);}else if(pivot + 1 < end){// 右边至少有两个元素stack.push(pivot + 1);stack.push(end);}// 找基准里面会互换元素进行排序while(!stack.empty()){end = stack.pop();start = stack.pop();pivot = partitionHoare(array,start,end);if(pivot - 1 > start){// 左边有两个元素stack.push(start);stack.push(pivot - 1);}else if(pivot + 1 < end){// 右边至少有两个元素stack.push(pivot + 1);stack.push(end);}}

归并排序

1. 分解：根据mid进行分解

2. 合并：第一个有序段和第二个有序段，比较大小放入一个新的数组中
   

// 归并排序public static void mergeSort(int[] array){merge(array,0,array.length - 1);}private static void merge(int[] array,int start,int end){if(start >= end){return;}int mid = (start + end) / 2;// 分解merge(array,start,mid);merge(array,mid + 1,end);// 合并mergeHeB(array,start,mid,end);}private static void mergeHeB(int[] array, int left, int mid, int right) {int s1 = left;int e1 = mid;int s2 = mid + 1;int e2 = right;// 新数组的下标int k = 0;int[] tmpArray = new int[right - left + 1];while(s1 <= e1 && s2 <= e2){if(array[s1] < array[s2]){tmpArray[k++] = array[s1++];}else{tmpArray[k++] = array[s2++];}}while(s1 <= e1){tmpArray[k++] = array[s1++];}while(s2 <= e2){tmpArray[k++] = array[s2++];}// left是因为有左边还有右边的数组// tmpArray是临时数组,会销毁的,需要拷贝回原来的数组for(int i = 0;i < tmpArray.length;i++){array[i + left] = tmpArray[i];}}

分析

1. 时间复杂度：O(N * logN)
2. 空间复杂度：O(N)，因为每次合并数组的时候要开O(N)大小的额外空间
3. 稳定性：稳定的排序

非递归实现归并排序

1. 先一个一个有序，两个两个有序，四个四个有序，八个八个有序…
2. gap = 1
   left = i
   mid = left + gap - 1
   right = mid + gap
   gap *= 2
3. 每组合并完，最终就有序了

// 非递归实现归并排序public static void mergeSortNor(int[] array){// gap表示每组的数据个数int gap = 1;while(gap < array.length){for(int i = 0;i < array.length;i = i + 2 * gap){int left = i;// mid和right可能会越界// 比如只有5个元素// 分解右边一半的时候// l = i mid = 5 r = 7int mid = left + gap - 1;int right = mid + gap;if(mid >= array.length){mid = array.length - 1;}if(right >= array.length){right = array.length - 1;}mergeHeB(array,left,mid,right);}gap *= 2;}}

海量数据的排序

1. 使用归并排序进行外部排序，如果内存中不够空间的话

非比较的排序

计数排序

1. 通过统计每次数字出现的次数，最后按照顺序从小到大输出这些数字
2. 适用的场景：指定范围内的数据

// 计数排序,指定范围内的数据进行排序
// O(Max(N，范围))public static void countSort(int[] array){int minVal = array[0];int maxVal = array[0];// O(N)for(int i = 0;i < array.length;i++){if(minVal > array[i]){minVal = array[i];}if(maxVal < array[i]){maxVal = array[i];}}int len = maxVal - minVal + 1;int[] count = new int[len];// O(N)for(int i = 0;i < array.length;i++){count[array[i] - minVal]++;}// 写回array数组中// O(范围)// 因为count数组集中于一个数字,那么也是O(范围)// 如果count数组不集中于一个数子,也是N倍的范围// 也是O(范围)int k = 0;for(int i = 0;i < count.length;i++){while(count[i] > 0){array[k++] = i + minVal;count[i]--;}}}

分析

1. 时间复杂度：O(Max(N，范围))
2. 空间复杂度：O(范围)
3. 稳定性：稳定的排序

基数排序

1. 开10个大小的空间，分别依次比较个位大小，十位大小和百位大小，最终达到有序，每个空间都是一个队列

桶排序

1. 先把数字放入一个范围的区间内进行排序，排好序依次拿出来，最终就有序了