【数据结构与算法】常见排序算法（Sorting Algorithm）

小明 2025-05-03 04:00:36 5

文章目录

  • 相关概念
  • 1. 冒泡排序（Bubble Sort）
  • 2. 直接插入排序（Insertion Sort）
  • 3. 希尔排序（Shell Sort）
  • 4. 直接选择排序（Selection Sort）
  • 5. 堆排序（Heap Sort）
  • 6. 快速排序（Quick Sort）
    • 6.1 hoare快排（最早的快排方法）
    • 优化快排（重要）
      • 1. 减少函数递归的栈帧开销（虽然不用，但必须了解）
      • 2.三位取中法取基准值（重点）
      • 6.2 挖坑法快排
      • 6.3 双指针法快排
      • 6.4 非递归快排
      • 快速排序的排序速度比较（包含测试代码）
      • 7. 归并排序（Merge Sort）
        • 7.1 递归版
        • 7.2 非递归版
        • 8. 计���排序

          相关概念

          1. 排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
          2. 稳定性：说简单点就是有相同值时，排序后这些相同值互相顺序没发生变化则称为稳定的排序算法。假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
          3. 内部排序：数据元素全部放在内存中的排序（重点）。
          4. 外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序（了解）。

          常见排序算法时间、空间、稳定性：

          1. 直接插入排序：O(n2)，正常情况下最快的O(n2)排序算法，稳定。
          2. 希尔排序：O(n1.3)，比O(n*log2n)慢一点点，不稳定。
          3. 直接选择排序：O(n2)，比冒泡快，比插入慢，不稳定。
          4. 堆排序：O(n*log2n)，不稳定。
          5. 冒泡排序：O(n2)，稳定。
          6. 快速排序： O(n*log2n)，不稳定，空间O(log2n)。
          7. 归并排序 O(n*log2n)，稳定，空间O(n)。

          排序不特别说明，则排序以升序为例。

          时间复杂度不特别说明，则默认最坏时间。

          空间复杂度不特别说明，则默认O(1)。

          1. 冒泡排序（Bubble Sort）

          思想：两两比较，再交换。前一个值比后一个值大，交换两个值。

          优化冒泡排序，冒泡排序优化版：

          void BubbleSort(int* a, int n) 
{
	int sortBorder = n - 1;
	int lastExchange = 0; 
	for (int i = 0; i  a[j + 1]) 
			{
				Swap(&a[j], &a[j + 1]);
				isSorted = false;
				lastExchange = j;
			}
		}
		if (isSorted) {
			break;
		}
		sortBorder = lastExchange;
	}
}
void Swap(int* px, int* py) 
{
	int tmp = *px;
	*px = *py;
	*py = tmp;
}

          2. 直接插入排序（Insertion Sort）

          思想：类似将扑克牌排序的过程，数据越有序，排序越快。

          void InsertionSort(int* a, int n)
{
	for (int i = 0; i = 0 && insertVal  

          直接插入排序O(n*n)，n方的排序中，直接插入排序是最有价值的。其它的如冒泡，直接选择排序等与直接插入排序一样N方的排序都是五十步和百步的区别，总体来看没啥区别，都不如直接插入排序，看以下几点分析以及排序时间比较，再就是大家自己编一串数据走查一下排序过程即可发现。
           

          1.排升序而数据大致是降序，或排降序而数据大致是升序情况下，直接插入排序的时间复杂度是O(n*n)，因为比较挪数据次数是等差数列之和。
           

          2.数据大致有序，且排序顺序与数据顺序一致情况下，直接插入排序的时间复杂度是O(n)，因为比较挪数据次数较少（不进入while循环）。比如排升序，而数据也大致也是升序状态（较为有序 或 直接就是有序的）。
           

          3.虽然直接插入排序与冒泡排序的时间复杂度是同一个量级，但不谈上面第一种情况，
          正常大多都是数据随机排列情况下前者比后者快很多，这时比较挪数据次数不会是等差数列之和，中间一般多少会有一部分是有序的，有那么几趟是不进入while循环的，比较挪数据次数当然是比等差数列之和要少的。虽然还是O(n*n)的量级，但明显是比冒泡快，至于快多少则是看有序的数据多不多（极限就是第二种情况）。
           

          10w个数据 排序速度对比：
           

          release环境是发布版本环境，对代码是有很大优化的，优化点大致是：
           

          1. 相比于debug环境，release环境生成的目标文件包含很少调试信息甚至没有调试信息。
          2. 减少了很多消耗性能或不必要的操作，不对代码进行边界检查，空指针检查、assert断言检查等。
          3. 特别是对递归优化巨大，也就是对函数栈帧的创建/栈的消耗优化很大，比如对于debug环境下栈溢出的程序，切换成release则不会造成栈溢出。
          博主水平有限，不知道更多相关细节或是底层原理，如有错误恳请指正。
           

          3. 希尔排序（Shell Sort）
           

          希尔排序是直接插入排序的优化版，对于直接插入排序而言，数据越有序，排序越快，希尔排序正是借助直接插入排序的特点进行了优化。
           

          思想：先对数据分组进行几次预排序（对数据分组进行直接插入排序），使数据形成较为有序的情况，最后整体进行一趟直接插入排序即可完成排序。
           

           

          void ShellSort(int* a, int n) 
{
	int gap = n; 
	while (gap > 1) {
		gap = gap / 3 + 1; // gap / 2也可
		for (int j = 0; j = 0 && insertVal  

          1.  
            希尔排序不好计算确切的时间复杂度，有牛人通过大量实验证明平均时间复杂度大致为O(n^1.3)，比O(n*logn)要慢一点点，但两者差不多是同一量级。
             
          2.  
            gap>1时是预排序，gap=1时等于直接插入排序。
             
          3.  
            gap的取值，gap/2或gap/3+1是当前主流，也被认为是gap最好的取值。gap相当于划分多少组进行预排序，如果定死gap=1则与直接插入排序无异。gap/2或gap/3+1则是划分每组多少个数进行预排序，gap/3+1中的+1是因为要保证最后一组排序时gap=1进行直接插入排序操作。严格来说只要能保证最后一趟gap=1，无论gap除以几加几，都算是希尔排序。
             
          4.  
            每一组预排序后，都会逐渐加大数据的有序情况。后面几组预排序虽然每组划分的数据多了（gap逐渐减小间隔变小了），也就是比较次数变多了，但经过前面的预排序后数据渐渐有序，实际不会进行过多的比较挪数据操作，每前一次预排序都为后一次预排序减轻压力。
             
          速度对比（毫秒）：
           

          4. 直接选择排序（Selection Sort）
           

          每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，逐步向后存放。
           

          数据较为有序的情况下，直接选择排序选要比冒泡、直接插入排序慢。
           

          void SelectionSort(int* a, int n)
{
	int begin = 0, end = n - 1;
	while (begin  

          在优化版中，必须有这样一个判断max==begin，并更新max的下标值！最小的数a[min]换到了左边begin位置，如果最大的数的下标max正好等于begin，那就出现这种问题：最大的数a[max]已经被换到min下标位置了，即a[min]才是最大数；而本来a[max]是最大的数，由于max==begin，而经过前面a[begin]与a[min]交换的影响，导致a[begin]/a[max]变成了最小的数，不加判断并更新max的后果是把最小的数放在右边end位置了。
           

          5. 堆排序（Heap Sort）
           

          了解堆请看：文章 堆 / 堆排序 / TopK问题（Heap）
           

          时间复杂度O(nlog2n)，排序速度与希尔差不多。也可以向上调整建堆，但比向下调整建堆要慢一些。
           

          void HeapSort(int* a, int n)
{
	for (int parent = (n - 1 - 1) / 2; parent >= 0; --parent) {
		AdjustDown(a, n, parent);
	}
	for (int end = n - 1; end > 0; --end)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
	}
}
/* 将堆向下调整为大堆 */
void AdjustDown(int* a, int size, int parent)
{
	int child = parent * 2 + 1; // 选出较大子节点
	child = child + 1  a[child]
		? child + 1 : child;
	while (child  a[parent])
	{
		Swap(&a[child], &a[parent]);
		parent = child; // 重复往下
		child = parent * 2 + 1;
		child = child + 1  a[child]
			? child + 1 : child;
	}
}

           

          parent初始为最后一个非叶子节点（多一个 -1 的原因），
          向下调整（建大堆），往堆顶方向走把所有非叶子结点调整一遍。
           

          堆顶最大值与堆底较小值交换，然后排除这个堆底的最大值(a[end])，
          剩下的作为堆，从堆顶较小值开始向下调整为大堆（–end一步步排除新的最大值a[end]）。
           

          10w个数据，排序速度对比：
          堆排序时间复杂度严格来算：
           

          1. 向上调整建堆O(nlogn) + 排序O(nlong)：O(2n*2logn)。
          2. 向下调整调整建堆O(n) + 排序O(nlogn)：O(2n*logn)。
          所以说希尔排序O(n1.3)比O(n*log2n)要慢些，但却是同一量级。不过堆排序的时间复杂度严格来说比真正的O(nlog2n)要慢一点点，所以希尔排序与堆排序的速度相同。
           

          6. 快速排序（Quick Sort）
           

          快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。
           

          6.1 hoare快排（最早的快排方法）
           

          基本思想：取待排序数据中的某个元素作为基准值，将数据分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后左右子序列重复该过程进行分割，直到所有元素都排列在相应位置上为止。
           

          // 1.hoare递归（最早的快排方法）
void QuickSort1(int* a, int begin, int end)
{
	if (begin ，
				--right; // 找小的
			}
			while (left
The End

标签：

微信