七大排序(Java)
目录
一、插入排序
1. 直接插入排序
2. 希尔排序
二、选择排序
1. 直接选择排序
2. 堆排序
三、交换排序
1. 冒泡排序
2. 快速排序
四、归并排序
五、总结
一、插入排序
1. 直接插入排序
抓一张牌,在有序的牌中,找到合适的位置并且插入。
- 时间复杂度:O(n^2)
- 空间复杂度:O(1)
- 稳定性:稳定
代码:
public static void insertSort(long[] array) {for (int i = 1; i < array.length; i++) {//认为第一个数已经有序,所以循环 n - 1 次long tmp = array[i];int j = i - 1;for(; j >= 0; j--) {if (array[j] > tmp) {array[j + 1] = array[j];} else {break;}}//j回退到了 小于0 的地方array[j + 1] = tmp;}}
2. 希尔排序
插入排序的升级版本,即进行大量的分组插排。
- 时间复杂度:O(n^1.3 ~ n^1.5)
- 空间复杂度:O(1)
- 稳定性:不稳定
代码:
//gap:组数public static void shell (int[] array, int gap) {for (int i = gap; i < array.length; i++) {int tmp = array[i];int j = i - gap;for (; j >= 0; j = j - gap) {if (array[j] > tmp) {array[j + gap] = array[j];} else {break;}}array[j + gap] = tmp;}}public static void shellSort(int[] array) {int gap = array.length;while (gap > 1) {shell(array,gap);gap = gap / 2;}shell(array, 1);}
二、选择排序
1. 直接选择排序
找到无序区间中最小的元素的下标,然后将该元素放到无序区间的开始(有序区间的最后)。
- 时间复杂度:O(n^2)
- 空间复杂度:O(1)
- 稳定性:不稳定
代码:
// array: 待排序区间public static void selectSort(int[] array) {for (int i = 0; i < array.length; i++) {int minIdx = i;for (int j = i + 1; j < array.length; j++) {if (array[j] < array[i]) {minIdx = j;}}swap(array, minIdx, i);}}
2. 堆排序
选择排序的升级版本。将无序区间维护成一个大堆(因为从小到达排序,需要大堆)。利用大堆,从无序区间中找到最大值,交换。
- 时间复杂度:O( N*log(N))
- 空间复杂度:O(1)
- 稳定性:不稳定
代码:
//堆排序public static void heapSort(int[] array) {//1.建堆 O(n)creatHeap(array);int end = array.length - 1;//2.交换然后调整 O(n * log(n))while (end > 0) {swap(array, 0, end);shiftDown(array, 0, end);end--;}}public static void creatHeap(int[] array) {for (int parent = (array.length - 1 - 1)/ 2; parent >= 0; parent--) {shiftDown(array, parent, array.length);}}public static void shiftDown(int[] array, int parent, int len) {int child = 2 * parent + 1; //左孩子下标while (child < len) {if (child + 1 < len && array[child] < array[child + 1]) {child++;}//child 下标为左右孩子中最大的孩子的下标if (array[child] > array[parent]) {swap(array, parent, child);parent = child;child = 2 * parent + 1;} else {break;}}}
三、交换排序
1. 冒泡排序
从前往后,两两元素进行比较,前者大于后者则交换。每次循环完一个元素,后面的有序区间就多加一个元素。
- 时间复杂度:O(N^2)
- 有序情况下:O(n)
- 空间复杂度:O(1)
- 稳定性:稳定
代码:
public static void bubbleSort(int[] array) {for (int i = 0; i < array.length - 1; i++) {boolean flag = false;for (int j = 0; j <array.length - 1 - i; j++) {if (array[j + 1] < array[j]) {swap(array, j, j + 1);flag = true;}}if (flag == false) {break;}}}
2. 快速排序
①在待排序区间内,选择一个基准值(pivot),本次代码中选择的是最右边;
②对待排序区间进行 partition 操作,目标:将待排序区间分开,左边的小于等于pivot,右边的大于等于pivot;
③分别再对左右两个小区间按照相同的方式进行处理。
- 时间复杂度:
- 最好【每次可以均匀的分割待排序序列】:O(N*log(N))
- 最坏:数据有序 或者逆序的情况 O(N^2)
- 空间复杂度:
- 最好:O(logN)
- 最坏:O(n) 单分支的一棵树
- 稳定性:不稳定
代码:
public static void quickSort(int[] array) {quick(array, 0, array.length - 1);}public static void quick(int[] array, int left, int right) {if (left >= right) {return;}int pivot = partition(array, left, right);quick(array, left, pivot - 1);quick(array, pivot + 1, right);}//挖坑法public static int partition(int[] array, int start, int end) {int tmp = array[start];while (start < end) {while(start < end && array[end] >= tmp) {end--;}//end位置的元素小于基准值,挖坑array[start] = array[end];while(start < end && array[start] <= tmp) {start++;}//start位置的元素大于基准值,挖坑array[end] = array[start];}array[start] = tmp;return start;}
由于用到了递归,当基准值左右边已经有序时,还需要栈空间来进行递归,所以当数据过大时,可能会导致栈溢出的情况,所以要将快速排序进行优化。
- 当待排序区间元素个数小于某个范围时,可以使用插入排序。
- 找基准值时,采用三数取中法。
代码:
public static void quickSort(int[] array) {quick(array, 0, array.length - 1);}public static void quick(int[] array, int left, int right) {if (left >= right) {return;}//优化1:元素小于某个区间时,使用插入排序if (right - left + 1 < 1400) {insertSort(array, left, right);}//优化2:三数取中法int MinIdx = FindMinIdx(array, left, right);swap(array, MinIdx, left);int pivot = partition(array, left, right);quick(array, left, pivot - 1);quick(array, pivot + 1, right);}//挖坑法public static int partition(int[] array, int start, int end) {int tmp = array[start];while (start < end) {while(start < end && array[end] >= tmp) {end--;}//end位置的元素小于基准值,挖坑array[start] = array[end];while(start < end && array[start] <= tmp) {start++;}//start位置的元素大于基准值,挖坑array[end] = array[start];}array[start] = tmp;return start;}//插入排序public static void insertSort(int[] array, int start, int end) {for (int i = 1; i < end; i++) {int tmp = array[i];int j = i - 1;for (; j >= start; j--) {if (array[j] > tmp) {array[j + 1] = array[j];} else {//array[j + 1] = tmpbreak;}}// j 回退到了小于 0 的位置//或者从 break 出来array[j + 1] = tmp;}}//三数取中法private static int FindMinIdx(int[] array, int start, int end) {int mid = start + ((end - start) >>> 1);if (array[start] < array[end]) {if (array[mid] < array[start]) {return start;} else if (array[mid] > array[end]) {return end;} else {return mid;}} else {if (array[mid] > array[start]) {return start;} else if (array[mid] < array[end]) {return end;} else {return mid;}}}public static void swap(int[] array, int p, int q) {int tmp = array[p];array[p] = array[q];array[q] = tmp;}
快速排序非递归版本:利用栈存储 left 和 right 的值。
public static void quickSort非递归(int[] array) {Deque<Integer> stack = new LinkedList<>();int left = 0;int right = array.length - 1;int pivot = partition(array, left, right);if (pivot > left + 1) {//左边有两位数stack.push(left);stack.push(pivot - 1);}if (pivot < right - 1) {stack.push(pivot + 1);stack.push(right);}while(!stack.isEmpty()) {right = stack.pop();left = stack.pop();pivot = partition(array, left, right);if (pivot > left + 1) {//左边有两位数stack.push(left);stack.push(pivot - 1);}if (pivot < right - 1) {stack.push(pivot + 1);stack.push(right);}}}
四、归并排序
归并排序是采用分治法的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
- 时间复杂度:O(N*log(N))
- 空间复杂度:O(n)
- 稳定性:稳定
在写归并排序代码之前,需要先会写:两个有序数组合并为一个有序数组。
代码:
//将两个有序数组合并为一个有序数组//array1 和 array2 均为有序数组public static int[] mergeArray(int[] array1, int[] array2) {int[] tmp = new int[array1.length + array2.length];int s1 = 0;int s2 = 0;int e1 = array1.length - 1;int e2 = array2.length - 1;int k = 0;while (s1 <= e1 && s2 <= e2){if (array1[s1] <= array2[s2]) {tmp[k++] = array1[s1++];//k++;//s1++;} else {tmp[k++] = array2[s2++];}}while (s1 <= e1) {tmp[k++] = array1[s1++];}while (s2 <= e2) {tmp[k++] = array2[s2++];}return tmp;}
归并排序代码:
public static void mergeSort(int[] array) {mergeSortInternal(array, 0, array.length - 1);}private static void mergeSortInternal(int[] array, int low, int high) {if (low >= high) {return;}int mid = low + ((high - low) >>> 1);mergeSortInternal(array, low, mid);mergeSortInternal(array, mid + 1, high);merge(array, low, mid, high);}public static void merge(int[] array, int low, int mid, int high) {int[] tmp = new int[high - low + 1];int k = 0;int s1 = low;int e1 = mid;int s2 = mid + 1;int e2 = high;while (s1 <= e1 && s2 <= e2) {if (array[s1] <= array[s2]) {tmp[k++] = array[s1++];} else {tmp[k++] = array[s2++];}}while (s1 <= e1) {tmp[k++] = array[s1++];}while (s2 <= e2) {tmp[k++] = array[s2++];}//普通的归并数组需要直接返回 tmp 数组//但是在归并排序中,要将 tmp 数组重新拷贝到 array 数组中,//并且考虑在右子树中合并时,不能覆盖左边已经合并好的元素for (int i = 0; i < k; i++) {array[low + i] = tmp[i];}}
非递归版本:
public static void mergeSort非递归(int[] array) {int nums = 1; //每组的数据个数while (nums < array.length) {for (int i = 0; i < array.length; i++) {int left = i;int mid = left + nums - 1;//防止越界if (mid >= array.length) {mid = array.length - 1;}int right = mid + nums;//防止越界if (right >= array.length) {right = array.length - 1;}//下标确定之后进行合并merge(array, left, mid, right);}nums *= 2;}}
五、总结
七大排序中:
稳定的排序:冒泡排序、插入排序、归并排序
插入排序主要看数组是否有序,来影响其时间复杂度
归并排序无论什么情况下,时间复杂度都为 O(N*log(N))
时间复杂度为O(N*log(N))的排序:快速排序、堆排序、归并排序
要想速度快就选 快速排序
要想稳定就选 归并
要想空间复杂度低就选 堆排序
排序 | 时间复杂度 | 空间复杂度 | 稳定性 |
插入排序 | O(N^2) | O(1) | 稳定 |
希尔排序 | O(N^1.3) | O(1) | 不稳定 |
选择排序 | O(N^2) | O(1) | 不稳定 |
堆排序 | O(N*log(N)) | O(1) | 不稳定 |
冒泡排序 | O(N^2) | O(1) | 稳定 |
快速排序 | O(N*log(N)) | O(log(N)) | 不稳定 |
归并排序 | O(N*log(N)) |
O(n) |
稳定 |