文章目录
- 前言
- 1. 排序的概念和引用
- 2.直接插入排序
- 3.希尔排序(缩小增量排序)
- 4. 直接选择排序
- 5. 堆排序
- 6. 冒泡排序
- 7.快速排序
- 7.1.Hoare法
- 7.2.挖坑法
- 7.3.快速排序的优化
- 7.4.非递归方法
- 8.归并排序
- 8.1.递归方法
- 8.2.非递归方法
- 8.3 海量数据的排序问题
- 9. 七大比较排序的复杂度以及稳定性分析
前言
我们这个博客讲一下七大基于比较的排序
其中算法的动态演示网站：
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
1. 排序的概念和引用
排序： 所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作
稳定性： 假设在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i] = r[j]，且r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的。
**内部排序：**数据元素全部放在内存中的排序
**外部排序：**数据元素太多不能同时放在内存中，根据排序过程的要求不能内外存之间移动数据的排序
排序算法：
- 基于比较的排序算法：
-
- 插入排序
-
-
- 直接排序
-
-
-
- 希尔排序
-
-
- 选择排序
-
-
- 选择排序
-
-
-
- 堆排序
-
-
- 交换排序
-
-
- 冒泡排序
-
-
-
- 快速排序
-
-
- 归并排序
- 基于非比较的排序算法：
-
- 计数排序
-
- 基数排序
-
- 统计数
2.直接插入排序
直接插入排序是一种简单的插入排序法，其基本思想：
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的小有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。实际中我们玩扑克牌时，就用了插入排序的思想。
当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置，便将array[i]插入，原来的位置上的元素顺序往后移动
插入排序
为了统一：下面所有的数字都是 从小到大排序。
思路：从数组下标为1开始(使用i变量)，进行排序，因为第一个数字(下标为0)本来就是有序的， 然后 用 tmp 变量保存 arr[i] (tmp = arr[i])，此时使用变量 j 来遍历 i 之前的子数组，因为该子数组是有序的，判断 arr[j] 和 tmp的大小，如果 arr[j] > tmp，此时 arr[j+1] = arr[j]，使得arr[j]往后移动，如果 arr[j] <= tmp，此时tmp找到了要填充的地方，arr[j+1] = tmp，然后break，因为已经可以确定 此时 子数组一定是有序的。如果都最后遍历完整个数组，都没有放好位置，那么说明 tmp 是最小的，此时 直接把 arr[j+1] = tmp，因为此时 j = -1
public static void insertSort(int[] array){
for(int i = 1;i<array.length;i++){
int tmp = array[i];
int j = i-1;
for (;j>=0;j--){
if (array[j] > tmp){
array[j+1] = array[j];
}else {
array[j+1] = tmp;
break;
}
}
array[j+1] = tmp;
}
}
直接插入排序的特性总结：
- 元素集合越接近有序，直接插入排序算法的时间效率越高
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
- 稳定性：稳定
3.希尔排序(缩小增量排序)
希尔排序法又称为缩小增量法。希尔排序法的基本思路：先选定一个整数，把待排序文件汇中所有记录分成多个组，所有距离一样的记录分在同一组内，并对每一组内的记录进行排序，然后，重复上述的分组和排序的工作。当达到=1时，记录在统一组内排好序。
思路：希尔排序的基本思路跟直接插入排序一样，主要就是牵扯到分组，下面我们来写一下带代码
希尔排序
public static void shellSort(int[] array){
int gap = array.length;
while (gap > 1){
// gap 不能大于等于 1，因为如果 gap = 1,此时进入循序，
// gap = 0，那么下面的shell 进入到死循环
gap /= 2;
shell(array,gap);
}
}
private static void shell(int[] array, int gap) {
for(int i = 0;i<array.length;i+=gap){
int tmp = array[i];
int j = i - gap;
for (;j>=0;j-=gap){
if (array[j] > tmp){
array[j+gap] = array[j];
}else{
array[j+gap] = tmp;
break;
}
}
array[j+gap] = tmp;
}
}
希尔排序的特性总结：
- 希尔排序是对直接排序的优化
- 当 gap > 1 时都是预排序，目的是让数组更接近于有序。当 gap == 1时，数组已经接近有序，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的优化。
- 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定
- 稳定性：不稳定
4. 直接选择排序
基本思路：
每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
还是以 从小到大进行排序
先从array[i] ~ array[n-1]中选择最小的数据元素
如果不是第一个元素(array[0])的话，就跟第一个元素进行交换，然后在剩余的数组中，重复上述操作，直到集合剩余一个元素
直接选择排序
public static void selectSort2(int[] array){
int n = array.length;
for(int i = 0;i<n;i++){
int minIndex = i;
for(int j = i+1;j < n;j++){
if (array[minIndex] > array[j]){
minIndex = j;
}
}
swap(array,minIndex,i);
}
}
private static void swap(int[] array, int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
上面这个代码是只找最小下标的值，下面是对上面的代码进行一次优化，从两边一起找。
下来我们编写代码：
public static void selectSort(int[] array){
int left = 0,right = array.length - 1;
while (left <= right){
int maxIndex = left,minIndex = left;
for (int i = left+1; i <= right; i++) {
if (array[i] > array[maxIndex]){
maxIndex = i;
}
if (array[i] < array[minIndex]){
minIndex = i ;
}
}
swap(array,minIndex,left);
if (maxIndex == left){
maxIndex = minIndex;
}
swap(array,maxIndex,right);
left++;
right--;
}
}
private static void swap(int[] array, int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
直接选择排序的特性总结：
- 直接选择排序思考非常好理解，但是效率不是很少，实际中很少使用
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
- 稳定性：不稳定
5. 堆排序
堆排序(HeapSort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法，他是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆
这个堆排序在咱们的Java(二十六)—优先级队列(堆)中提及到了，载着我们再讲一遍，并且从小到大进行排列
堆排序
下来我们来编写代码：
public static void heapSort(int[]array){
createHeap(array);
int end = array.length-1;
while (end > 0){
swap(array,0,end);
shitDown(array,0,end);
end--;
}
}
private static void shitDown(int[] array, int parent, int length) {
int child = 2 * parent + 1;
while (child < length){
// 用来判断 child + 1 这个是否合法，并且判断 child 和 child + 1 谁大谁小
if (child + 1 < length && array[child] < array[child + 1]){
child++;
}
if (array[child] > array[parent]){
swap(array,child,parent);
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--){
shitDown(array,parent, array.length);
}
}
private static void swap(int[] array, int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
堆排序的特性总结
- 堆排序使用堆来选数，效率就高了很多
- 时间复杂度：O(n*logn)
- 空间复杂度：O(1)
- 稳定性：不稳定
6. 冒泡排序
冒泡排序
上面就是冒泡排序的流程图
其中定义一个变量 i ，用于记录排序的趟数，j用于交换两个数，下面我们编写一下代码
public static void bubbleSort(int[] array){
for (int i = 0;i<array.length-1;i++){
for (int j = 0;j<array.length-i-1;j++){
if (array[j] > array[j+1]){
swap(array,j,j+1);
}
}
}
}
private static void swap(int[] array, int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
其中我们还可以进行优化
我们添加一个变量 flg，用于记录这一趟是否进行了交换元素的操作，如果这一趟没有交换元素，那么说明后面的元素都是有序的，因此这一趟提前就结束，直接break
public static void bubbleSort(int[] array){
for (int i = 0;i<array.length-1;i++){
boolean flg = false;
for (int j = 0;j<array.length-i-1;j++){
if (array[j] > array[j+1]){
swap(array,j,j+1);
flg = true;
}
}
if (!flg){
break;
}
}
}
private static void swap(int[] array, int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
冒泡排序的特性总结：
- 冒泡排序是一种非常容易理解的排序
- 时间复杂度:O(N^2)
- 空间复杂度：O(1)
- 稳定性：稳定
7.快速排序
快速排序是 Hoare 于1962年提出的一种二叉树交换排序的方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两个字序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后左右子序列重复该过程，直到所有元素都排列在相应位置上为止
快速排序
这个便是大致的流程.
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 pivot = partition(array,start,);
quick(array,start,pivot-1);
quick(array,pivot+1,end);
}
上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，同学们在写递归框架时可想想二叉树前序
遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。
将区间按照基准值划分为左右两半部分的常见方式有：
7.1.Hoare法
private static int partition(int[] array, int left, int right) {
int tmpleft = left;
int pivot = array[left];
while (left < right){
while (left < right && array[right] >= pivot){
right--;
}
while (left < right && array[left] <= pivot){
left++;
}
swap(array,left,right);
}
swap(array,tmpleft,left);
return left;
}
其中有两个小细节问题，给大家说一下：
- 为什么要先从后往前找下一个right，而不是先从前往后中找下一个left
我们就动态演示一下呗。
此时我们发现，9这个数字竟然在 6 的左边，显然不符合我们的预期，因此不能这样写 - 为什么是array[right] >= pivot，而不是array[right] > pivot
需要考虑循环问题
7.2.挖坑法
下面我们根据上面的图，来编写一下代码
/*
挖坑法
*/
private static int partition(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;
}
7.3.快速排序的优化
- 三数取中法选 key
顾名思义，就是从left ，right，以及这两个元素的一半数，查找中间的数，让他成为一个基准值，这样就可以快速提高效率
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 midIndex = getMiddle(array,start,end);
swap(array,midIndex,start);
int pivot = partition(array,start,end);
quick(array,start,pivot-1);
quick(array,pivot+1,end);
}
private static int getMiddle(int[]array,int left,int right) {
int mid = (left + right)/2;
if (array[left] < array[right]){
if (array[mid] < array[left]){
return left;
} else if (array[right] < array[mid] ) {
return right;
}else {
return mid;
}
}else {
if (array[right] < array[mid]){
return right;
}else if (array[mid] > array[left]){
return left;
}else {
return mid;
}
}
}
/*
挖坑法
*/
private static int partition(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;
}
private static void swap(int[] array, int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
- 递归到小的子区间中，可以考虑使用插入排序
我们知道，直接插入排序，数组越有序，排序的速度越快，例如，当子数组的长度只剩下5个之后，选择插入排序，下面我们写一下代码
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;
}
if (end - start + 1 <= 5){
insertSortRange(array,start,end);
return;
}
int midIndex = getMiddle(array,start,end);
swap(array,midIndex,start);
int pivot = partition(array,start,end);
quick(array,start,pivot-1);
quick(array,pivot+1,end);
}
private static void insertSortRange(int[] array, int start, int end) {
for(int i = start + 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] = tmp;
break;
}
}
array[j+1] = tmp;
}
}
7.4.非递归方法
public static void quickSort(int[] array){
quickNor(array,0,array.length-1);
}
public static void quickNor(int[] array,int start,int end) {
Stack<Integer> stack = new Stack<>();
int pivot = partition(array,start,end);
if (pivot > start + 1){
stack.push(start);
stack.push(pivot-1);
}
if (pivot < end - 1){
stack.push(pivot+1);
stack.push(end);
}
while (!stack.isEmpty()){
end = stack.pop();
start = stack.pop();
pivot = partition(array,start,end);
if (pivot > start + 1){
stack.push(start);
stack.push(pivot-1);
}
if (pivot < end - 1){
stack.push(pivot+1);
stack.push(end);
}
}
}
快速排序总结：
- 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫做 快速 排序
- 时间复杂度：O(n*logn)
- 空间复杂度：O(logn)
- 稳定性：不稳定
8.归并排序
归并排序(merge-sort)是建立在归并排序操作上的一种有效的排序算法，算法采用分治法(Divide and Conquer)
归并排序
8.1.递归方法
前面的分解操作，属于递归操作，跟上面的快速排序一样，在这就不做讨论
下面的是合并：这个操作也比较简单，大家看一下下面的代码，自行领悟一下
public static void mergeSort(int[]array){
mergeSortTmp(array,0,array.length-1);
}
private static void mergeSortTmp(int[] array, int left, int right) {
if (left > right) {
return;
}
int mid = (left + right)/2;
// 分解操作：递归
mergeSortTmp(array,left,mid);
mergeSortTmp(array,mid+1,right);
// 合并：合并两个有序数组
merge(array,left,mid,right);
}
private static void merge(int[] array, int left, int mid, int right) {
int[] tmp = new int[right - left + 1];
int k = 0;
int s1 = left,e1 = mid,s2 = mid+1,e2 = right;
while (s1 <= mid && s2 <= right){
if (array[s1] <= array[s2]){
tmp[k++] = array[s1++];
}else {
tmp[k++] = array[s2++];
}
}
while (s1 <= mid){
tmp[k++] = array[s1++];
}
while (s2 <= right){
tmp[k++] = array[s2++];
}
for (int i = 0; i < k;i++){
array[i+left] = tmp[k];
}
}
8.2.非递归方法
上面递归的逻辑，主要是找到 left right mid的位置，只要找到 这三个位置，就可以调用 merge 方法
使用 gap 来表示 每个分组的数组内元素个数，left = i，mid = left + gap -1，right = mid + gap
然后 把这三个参数放到 merge 方法中
public static void mergeSort(int[]array){
//mergeSortTmp(array,0,array.length-1);
mergeSortNor(array);
}
private static void mergeSortNor(int[] array) {
int gap = 1;
while (gap < array.length){
for (int i = 0;i<array.length;i = i + gap * 2){
int left = i;
int mid = left + gap - 1;
if (mid > array.length){
mid = array.length - 1;
}
int right = mid + left;
if (right > array.length){
right = array.length - 1;
}
merge(array,left,mid,right);
}
gap *= 2;
}
}
private static void merge(int[] array, int left, int mid, int right) {
int[] tmp = new int[right - left + 1];
int k = 0;
int s1 = left,e1 = mid,s2 = mid+1,e2 = right;
while (s1 <= mid && s2 <= right){
if (array[s1] <= array[s2]){
tmp[k++] = array[s1++];
}else {
tmp[k++] = array[s2++];
}
}
while (s1 <= mid){
tmp[k++] = array[s1++];
}
while (s2 <= right){
tmp[k++] = array[s2++];
}
for (int i = 0; i < k;i++){
array[i+left] = tmp[k];
}
}
归并排序总结
- 归并排序的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
- 时间复杂度：O(N*logN)
- 空间复杂度：O(N)
- 稳定性：稳定
8.3 海量数据的排序问题
外部排序：排序过程需要在磁盘等外部存储进行的排序
前提：内存只有 1G，需要排序的数据有 100G
因为内存中无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序
- 先把文件切分成 200 份，每个 512M
- 分别对 512M M排序。
- 进行二路归并，同时对2000份有序文件做归并过程，最终结果就有序了
9. 七大比较排序的复杂度以及稳定性分析
| 排序方法 | 最好 | 平均 | 最坏 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 插入排序 | 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^1.3) | O(n^2) | O(1) | 不稳定 |
| 堆排序 | O(n*logn) | O(n*logn) | o(n*logn) | O(1) | 不稳定 |
| 快速排序 | O(n*logn) | O(n*logn) | O(n^2) | O(logn) - O(n) | 不稳定 |
| 归并排序 | O(n*logn) | O(n*logn) | O(n*logn) | O(n) | 稳定 |
完
