排序
排序概念
- 排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
- 平时的上下文中，如果提到排序，通常指的是排升序（非降序）。
- 通常意义上的排序，都是指的原地排序(in place sort)。
稳定性
如果当前这个排序，在排序过程中，没有发生跳跃式的交换，那么我们就认为这个排序是稳定的
注意：
一个排序如果是稳定的排序，那么它也可以被时限为一个不稳定的排序
但是如果一个排序本身就是不稳定的排序，那么不可能实现为一个稳定的排序
总览图
(一) 冒泡排序
实现原理
在无序区间，通过相邻数的比较，将最大的数冒泡到无序区间的最后，持续这个过程，直到数组整体有序
代码实现
public static void bubbleSort(int[] array) {
for (int i = 0; i < array.length-1; i++) {
boolean isSort = true;
for (int j = 0; j < array.length-1-i; j++) {
if(array[j] > array[j+1]) {
int tmp = array[j];
array[j] = array[j+1];
array[j+1] = tmp;
isSort = false;
}
}
if(isSort) break;
}
}
性能分析
时间复杂度：
- 最好：数组有序：O(n)
- 最坏：数组逆序：O(n^2)
- 平均：O(n^2)
空间复杂度：O(1)
稳定性：稳定
(二) 选择排序
实现原理
每一次从无序区间选出最大（或最小）的一个元素，存放在无序区间的最后（或最前），直到全部待排序的数据元素排完 。
代码实现
public static void selectSort(int[] array) {
for(int i = 0; i < array.length; i++) {
for (int j = i+1; j < array.length; j++) {
if(array[j] < array[i]) {
int tmp = array[j];
array[j] = array[i];
array[i] = tmp;
}
}
}
}
分析与总结
时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：不稳定
补充：双向选择排序
和选择排序的思路一致，只不过两个变量分别从首尾向中间出发，每次找到左半边最小的交换 和 右半边最大的交换，这样可以减少一些时间复杂度
public static void selectSortOP(int[] array) {
int low = 0;
int high = array.length - 1;
// [low, high] 表示整个无序区间
// 无序区间内只有一个数也可以停止排序了
while (low <= high) {
int min = low;
int max = high;
for (int i = low + 1; i <= max; i++) {
if (array[i] < array[min]) {
min = i;
}
if (array[i] > array[max]) {
max = i;
}
}
swap(array, min, low);
if (max == low) {
max = min;
}
swap(array, max, high);
low++;
high--;
}
}
(三) 插入排序
实现原理
整个区间被分为
- 有序区间
- 无序区间
每次选择无序区间的第一个元素，在有序区间内选择合适的位置插入
代码实现
public static void insertSort(int[] array) {
int tmp = 0;
for(int i = 1; i < array.length; i++) {
tmp = array[i];
int j;
for (j = i-1; j >= 0; j--) {
if(array[j] > tmp) {
array[j+1] = array[j];
}else {
break;
}
}
array[j+1] = tmp;
}
}
优化代码
我们不难发现，在有序区间选择数据应该插入的位置时，因为区间的有序性，所以可以利用折半查找的思想
在这里插入代码片
性能分析
时间复杂度：
- 最好情况下：当数据是无序的情况下：O(n^2)
- 最坏情况下：当数据有序的时候，可以达到O(n^2)
结论：越有序，越快
另外：直接插入排序一般也会用到一些排序的优化上
空间复杂度： O(1)
稳定性： 稳定的排序
(四) 希尔排序
实现原理
希尔排序法又称缩小增量法。
希尔排序法的基本思想是：
先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。
- 希尔排序是对直接插入排序的优化。
- 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很
快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比
注意：
此增量序列是一个比较复杂的数学问题，没有固定的答案，
但是必须使增量序列中的值没有除 1 以外的公因子，把那个且最后一个增量值必须等于 1
代码实现
public static void shellSort(int[] array) {
int[] drr = {
5,3,1};
for (int i = 0; i < drr.length; i++) {
shell(array,drr[i]);
}
}
public static void shell(int[] array, int gap) {
for (int i = gap; i < array.length; i++) {
int tmp = array[i];
int j;
for (j = i-gap; j >= 0; j -= gap) {
if(array[j] > tmp) {
array[j+gap] = array[j];
}else {
break;
}
}
array[j+gap] = tmp;
}
}
性能分析
时间复杂度：
- 最好情况：O(n)
- 平均情况：O(1.3n) - O(1.5n)
- 最坏情况：O(n^2)
空间复杂度：O(1)
稳定性：不稳定
(五) 堆排序
实现原理
思路：
- 我们如果想要从小往大排序，则建立大根堆
- 我们如果想要从大往小排序，则建立小根堆
逻辑：
- 我们交换首位的位置
- 然后向下调整尾位置以前的堆
- 循环到尾指针 == 0 时，排序结束
这样我们就保证了每次最大的元素放到了最后的位置，全部循环完毕后，则时从小到大排序的
代码实现
public static void creatBigHeap(int[] array) {
int len = array.length-1;
int parent = (len-1)/2;
for (int i = parent; i >= 0; i--) {
adjustDown(i,array,len);
}
}
public static void adjustDown(int parent, int[] array,int end) {
int child = 2*parent+1;
while (child < end+1) {
if(child+1 <= end && array[child] < array[child+1]) {
child = child+1;
}
if(array[child] > array[parent]) {
int tmp = array[child];
array[child] = array[parent];
array[parent] = tmp;
parent = child;
child = parent*2+1;
}else {
break;
}
}
}
public static void heapSort(int[] array) {
creatBigHeap(array);
int end = array.length-1;
while (end >= 0) {
int tmp = array[0];
array[0] = array[end];
array[end] = tmp;
end--;
adjustDown(0,array,end);
}
}
性能分析
时间复杂度：O(n * logn)
空间复杂度：O(1)
稳定性：不稳定
(六) 快速排序
实现原理
分治思想
- 从待排序区间选择一个数，作为基准值(pivot)；
- Partition: 遍历整个待排序区间，将比基准值小的（可以包含相等的）放到基准值的左边，将比基准值大的（可
以包含相等的）放到基准值的右边； - 采用分治思想，对左右两个小区间按照同样的方式处理，直到小区间的长度 == 1，代表已经有序，或者小区间的长度 == 0，代表没有数据
代码实现–递归
public static void quickSort(int[] array) {
quick(array,0,array.length-1);
}
public static void quick(int[] array, int low, int high) {
if(low >= high) return;
int index = pivot(array,low,high);
quick(array,low,index-1);
quick(array,index+1,high);
}
public static int pivot(int[] array, int left, int right) {
int piv = array[left];
while (left < right) {
while (left < right && array[right] >= piv) {
right--;
}
array[left] = array[right];
while (left < right && array[left] <= piv) {
left++;
}
array[right] = array[left];
}
array[left] = piv;
return left;
}
代码实现–非递归
//相遇点
public static int pivot(int[] array, int left, int right) {
int piv = array[left];
while (left < right) {
while (left < right && array[right] >= piv) {
right--;
}
array[left] = array[right];
while (left < right && array[left] <= piv) {
left++;
}
array[right] = array[left];
}
array[left] = piv;
return left;
}
//快速排序---非递归
public static void quickSort(int[] array) {
Stack<Integer> stack = new Stack<>();
int low = 0;
int high = array.length-1;
stack.push(low);
stack.push(high);
while (!stack.isEmpty()) {
high = stack.pop();
low = stack.pop();
int index = pivot(array,low,high);
if(low+1 < index) {
stack.push(low);
stack.push(index-1);
}
if(high-1 > index) {
stack.push(index+1);
stack.push(high);
}
}
}
性能分析
分治思想 什么时候效率最高：当每次把待排序的序列 均匀划分的时候
时间复杂度：
- 最好情况：O(n * log(n))
- 最坏情况：O(n^2)
- 平均情况：O(n * log(n))
空间复杂度：
- 最好情况：O(n^2)
- 最坏情况：O(n)
- 平均情况：O(n^2)
稳定性：不稳定
优化
随机选取基准法
做法：随机找到后面的一个下标，然后和 low 下标的数据进行交换，最后以 low 下标交换后的值作为基准
三数取中法
做法：我们分别取到 首下标 low，尾下标 high，中间下标为 mid = (low+high)/2，最终将 mid 作为基准来选取
范围缩小插入法
当范围越来越小，则越来越趋于有序，越有序，插入排序的时间复杂度越低，所以可以定义，区间数据量低于某个值时，使用插入排序进行优化
详细的优化方法可以看这位博主的文章：
https://blog.csdn.net/insistgogo/article/details/7785038
(七) 归并排序
实现原理
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并
代码实现–递归
public static void merge(int[] array,int low,int mid,int high) {
int s1 = low;
int s2 = mid+1;
int[] tmp = new int[high-low+1];
int i = 0;
while (s1 <= mid && s2 <= high) {
if(array[s1] <= array[s2]) {
tmp[i++] = array[s1++];
}else {
tmp[i++] = array[s2++];
}
}
//可能s1没走完，也可能s2没走完
while (s1 <= mid) {
tmp[i++] = array[s1++];
}
while (s2 <= high) {
tmp[i++] = array[s2++];
}
for (int j = 0; j < tmp.length; j++) {
array[j+low] = tmp[j];
}
}
public static void mergeSortInternal(int[] array,int low,int high) {
if(low >= high) return;
int mid = (low+high)/2;
mergeSortInternal(array,low,mid);
mergeSortInternal(array,mid+1,high);
//合并
merge(array,low,mid,high);
}
public static void mergeSort(int[] array) {
int low = 0;
int high = array.length-1;
mergeSortInternal(array,low,high);
}
代码实现–非递归
public static void merge(int[] array,int gap) {
int s1 = 0;
int e1 = s1 + gap - 1;
int s2 = e1 + 1;
int e2 = s2 + gap - 1 < array.length ? s2 + gap - 1 : array.length - 1;
int[] tmp = new int[array.length];
int i = 0;
while (s2 < array.length) {
while (s1 <= e1 && s2 <= e2) {
if (array[s1] <= array[s2]) {
tmp[i++] = array[s1++];
}else {
tmp[i++] = array[s2++];
}
}
while (s1 <= e1) {
tmp[i++] = array[s1++];
}
while (s2 <= e2) {
tmp[i++] = array[s2++];
}
s1 = e2 + 1;
e1 = s1 + gap - 1;
s2 = e1 + 1;
e2 = s2 + gap - 1 < array.length ? s2 + gap - 1 : array.length - 1;
}
while (s1 < array.length) {
tmp[i++] = array[s1++];
}
for (int j = 0; j < tmp.length; j++) {
array[j] = tmp[j];
}
}
public static void mergeSort(int[] array) {
for (int i = 1; i < array.length; i*=2) {
merge(array,i);
}
}
海量数据排序
外部排序：排序过程需要在磁盘等外部存储进行的排序
前提：内存只有 1G，需要排序的数据有 100G
因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序
- 先把文件切分成 200 份，每个 512 M
- 分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以
- 进行 200 路归并，同时对 200 份有序文件做归并过程，最终结果就有序了
性能分析
时间复杂度：O(n * log(n))
空间复杂度：O(n)
稳定性：稳定
七大排序性能对比
| 排序方法 | 最好 | 平均 | 最坏 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 |
| 插入排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 希尔排序 | O(n) | O(n^1.3) | O(n^2) | O(1) | 不稳定 |
| 堆排序 | O(n * log(n)) | O(n * log(n)) | O(n * log(n)) | O(1) | 不稳定 |
| 快速排序 | O(n * log(n)) | O(n * log(n)) | O(n^2) | O(log(n)) ~ O(n) | 不稳定 |
| 归并排序 | O(n * log(n)) | O(n * log(n)) | O(n * log(n)) | O(n) | 稳定 |
小伙伴们学会了 一键三连 支持一下博主呀
转载：https://blog.csdn.net/starry1441/article/details/116349522
查看评论