一篇文章弄懂数据结构中的各种排序_插入排序_冒泡排序_快速排序_堆排序_归并排序_基数排序

一篇文章弄懂数据结构中的各种排序

1.排序的概念

排序：将各元素按关键字递增或递减顺序重新排列
评价指标：
稳定性：关键字相同的元素经过排序后相对顺序是否会发生改变。
注意：稳定性跟算法的优劣无关
时间复杂度，空间复杂度

分类：
内部排序：数据都在内存中
外部排序：数据太多，无法全部存入内存。

2. 插入排序

2.1 直接插入排序

算法思想：
从头开始，每次将一个待排序的记录，按照关键字大小加入到前面已经排好的子序列中。

流程是：
一个待排序的记录，从已经排好的子序列的尾部开始比较，找到小于或等于它的值，将其插入进去，得到新的子序列。

空间复杂度： O(1)
时间复杂度
最好时间复杂度（全部有序）：O(n)
最坏时间复杂度（全部逆序）：O(n²)
平均时间复杂度：O(n²)

算法稳定性：稳定

2.2 折半插入排序

前面说的插入排序，是通过顺序的方式查找需要插入的位置，由于子序列已经是顺序的，可以优化成通过折半(二分）查找插入位置。

比起“直接插入排序”，比较关键字的次数减少了，但是移动元素的次数没变，整体来看时间复杂度依然是o(n²)

对链表进行插入排序
虽然对链表进入插入排序移动的次数变少了，但是关键字对比的次数依然是O(n²)树数量级，时间复杂度依然是O(n²)

2.3 希尔排序

引入希尔排序：

我们不难发现插入排序最适合用于已经有序的序列，或者部分有序有序的序列。
希尔排序就是让部分有序-直接插入-部分有序–直接插入 的过程

算法思想：
先将待排序表分割成若干特殊子表，对每个子表进行直接插入的过程。

如何划分？
每一次划分设置一个增量d，如d=4，就是把相隔距离=4的元素，化为一组，如 1，5，9…，为一组2，6，10，为一组，以此类推，希尔建议每次设置增量后，下一次取增量取上一次增量的一半，但是在实际的解题中，要看具体要求，具体情况具体分析。

性能分析：
空间复杂度：o(1)
时间复杂度：无法计算，但优于直接插入排序
稳定性：不稳定
适用性：仅适用于顺序表，不适用于链表

3.冒泡排序

3.1 算法原理

算法原理：
每次从后往前后或从前往后，两两一组，逐次比较，如果后一个更小(从后往前）,则交换它们，注意，整个过程中，元素只交换，容纳两个元素的窗口移动。

每一趟比较都可以使一个元素移动到最终位置，已经确定最终位置的元素在之后的比较中无需再对比。

如果某一趟排序过程中未发生交换，则算法可提前结束。

代码思路:
两层循环，最外层保证，每一次循环让一个元素移动到最后一个位置，故n-1次就能保证n-1个元素都在最后的位置上，故n个元素都在最后的位置上。

for(int i=0;i<n-1;i++)

内层每次和最后一个元素j比较，若最后一个元素小，则和j-1交换，逐步往前遍历，小就交换，不小就遍历，直到到达最终位置。

for(int j=n-1;j>i;j--)
{if(a[j]<a[j-1]){swap(a[j],a[j-1]); //伪代码}
}

优化是定一个布尔变量flag，若一次循环并未改变flag的值，则直接退出循环

给出一个完整的c语言冒泡排序的算法：

 for(int i=0;i<numsSize-1;i++) {for(int j=0;j<numsSize-1-i;j++){if(nums[j]>nums[j+1]){int temp=0;temp=nums[j+1];nums[j+1]=nums[j];nums[j]=temp;}}}

3.2 性能分析

空间复杂度：o(1)

时间复杂度：
最好：o(n)
最差：o(n²)
平均：o(n²)

稳定性：稳定

适用性：顺序表，链表都可以。

4.快速排序

4.1 算法原理

首先将最左边待排元素移出数组，最左边设置low指针，最右边设置high指针，两边交替使用，从high指针开始移动，判断当前high指针所指向元素，是否大于待排元素，如果小于，则继续向左移动，继续比较，如果小于，则将该元素，移入到low指针指向的空间中，然后开始移动low指针，进行low指针的判断，此时low与high指针的职能交换。然后彼此互换。

快速排序代码如下:

int partition(int a[],int low,int high)
{int pivot=a[low];while (low<high) {while(a[high]>=pivot&&low<high){high--;}  //出循环之后，要移动high指向的元素赋值给low中空下来的位置a[low]=a[high];while(a[low]<=pivot&&low<high){low++;}a[high]=a[low];}a[low]=pivot;return low;  //此时low=high
}void quicksort(int a[],int low,int high)
{if(low<high){int pivot=partition(a, low, high);quicksort(a, low, pivot-1);quicksort(a, pivot+1, high);}
}

4.2 性能分析

空间复杂度：

• 最好：O(n)
• 最坏：O(logn)

空间复杂度：递归工作栈，确定空间复杂度

时间复杂度：
最好：O(n²)
最坏：O(n logn)
平均：O(n long)

稳定性：不稳定

5. 选择排序

5.1 简单选择排序

每一趟在待排序元素选取关键字最小的元素加入有序子序列。

算法性能分析：
空间复杂度：o(1)

时间复杂度：o(n²)
总共需要对比关键字：n(n-1)/2

稳定性：不稳定

适用性：既可以用于顺序表，也可用于链表

5.2 堆排序

什么是堆？
大根堆，意味着根最大，根结点大于它的左右结点，同理，每一个结点都满足这个性质，我们就把这个树形结构叫做大根堆。
小根堆反之。

5.1 算法流程

1️⃣建立大根堆

把所有非终端结点都检查一遍，是否满足大根堆的要求，如果不满足，则从后往前进行调整。
检查当前结点是否满足根>=左右，若不满足，则当前结点与更大的一个孩子互换
若元素互换破坏了下一级的堆，则采用相同的方法继续往下调整(小元素不断“下坠”）

2️⃣取根结点加入有序子序列(结果），并将待排序序列中的最后一个元素交换(肯定是当前的一个叶子结点）。然后回到1️⃣

5.2 算法效率分析

一个结点，每下坠一层，最多只需比较关键字2次。
若树高为h，某结点在第i层，则将这个结点向下调整最多只需要下坠h-i层，关键字对比次数不超过2(h-i）

建堆的过程，关键字对比次数不超过4n，建堆时间复杂度=o(n).
2️⃣的过程，时间复杂度是O(nlog₂n)
总的时间复杂度=O（nlogn）

稳定性：不稳定
基于大根堆的堆排序得到递增序列，基于小根堆得到递减序列。

5.3 堆排序的插入和删除操作(了解)

5.3.1 堆排序的插入操作

新元素放到表尾(堆底）
根据大/小根堆堆要求，新元素不断上升，直到无法继续上升为止。

每次上升调整只需对比关键字1次

5.3.2 堆排序的删除操作

被删除元素用表尾(堆底）元素代替
根据大/小根堆堆要求，替代元素不断下坠，直到无法继续下坠为止。

每次下坠调整可能需要对比关键字2次，也可能只需对比1次。

5.4 代码实现堆排序

void swap(int *a, int *b)
{int temp = *a;*a=*b;*b=temp;
}void heapify(int a[],int length,int i)
{//找到当前结点和它的左右孩子孩子中最大的一个，将最大的结点与当前结点交换，若当前结点就是最大的，则不交换int largest=i;int lson=i*2+1;int rson=i*2+2;if(lson<length&&a[largest]<a[lson]) largest=lson;         //左右孩子不能超出这个树的范围<lif(rson<length&&a[largest]<a[rson]) largest=rson;if(largest!=i){swap(&a[i], &a[largest]);heapify(a,length,largest);}
}void heap_sort(int a[],int length)
{//堆排序的大体过程，首先建立堆，然后将当前的根节点和最大下标的叶子结点，交换，然后将新的叶子结点删除，并且重新调整堆// 第一步，建立堆，遍历全部的非叶子结点，从下往上的遍历，调整，确保一遍完成建立堆堆操作//因为是从0开始存储，对应的父结点下标是length/2-1，假如从1开始存储，就是length/2for(int i=length/2-1;i>=0;i--) //从最后一个非叶子结点开始，遍历全部的非叶子结点，此时的就能找到最大的值放在根上{heapify(a, length, i);}//第二步开始，多次调整堆,每一次都会确定一个位置，即将当前的根与最后一个叶子结点交换，再重新进行建堆操作for(int i=length-1;i>0;i--){swap(&a[0], &a[i]); //a[0]是最大的那个，a[i]是当前要确定的位置heapify(a, i, 0); //当前的长度就是i，当前要从根开始调整;}}

6. 归并排序

6.1 算法思想和算法流程

算法思想：
把两个或多个已经有序的序列合并成一个序列，合并的过程，就是两个有序序列依次对比把更小(或更大的拿出来合并）。

算法流程：
以二路归并为例

从每一个元素都是一个队列开始都是一个独立的有序序列，相邻两个元素合并成一个，在排好序，以此类推，不断将相邻的两个有序序列合并并排好序，直到就剩一个有序序列为止。

6.2 算法效率分析

算法的空间复杂度：O(n)
算法的时间复杂度：O(nlogn)
稳定性：稳定的

7. 基数排序

7.1 算法思想和算法流程

算法思想：
不比较关键字，而是按位数比较，比如给多个三位数排序，就先比较它们的个位数，再比较它们的十位数，最后比较它们的百位数。

算法流程：
以多个三位数的比较为例

首先设置十个队列，因为0-9是10个数

从左往右，根据个位数的，将相应的个位数加入队列中，然后再从左往右，把各个队列拿出来拼到一起

上面个位数就排好列，再排十位数，如法炮制，最后排百位数

7.2 算法效率分析

n是元素个数，d是趟数，比如三位数就是三趟，r是辅助队列的个数，比如0-9就是10个

空间复杂度：o(r)
时间复杂度：o(d(n+r))
稳定性：稳定
擅长处理什么样的问题？
n大，但是r和d小的问题

8.例题

堆排序

快速排序

真题1:


真题2:

希尔排序

希尔排序中，值得注意的点是，一个数据可能被多次的比较，比如d=5，第一个和第六个元素比较，等到了第6个元素，第6个元素再与第11个元素比较（如果存在第11个元素的话）