排序

排序就是重新排列表中的元素，使表中的元素满足按关键字有序的过程

稳定性：在排序前相同的的两个元素，在排序后如果前后顺序没有改变，则是稳定，如果发生了改变，则不稳定

排序可以分为内部排序和外部排序，内部排序的数据都在内存中，考虑时空复杂度，而外部排序发生在磁盘和内存中，要考虑到尽可能降低读写次数

插入排序

插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
		//插入排序
void InsertSort(int x[],int n) {
	int temp, j, i;
	for (i = 1; i < n; i++)     
	{
		if (x[i] < x[i - 1]) {  //如果x[i]小于前驱,保证了稳定性
			temp = x[i];              //暂存x[i]
			for (j = i ; j >0 && x[j-1] > temp; j--)
                //在之前的序列中，找到x[i]的位置，如果x[j-1]<=x[i]了，那么j正好就是插入位置 
			{                     
				x[j] = x[j-1];             //大于x[i]的数向后移位
			}
			x[j] = temp;                   //插入
		}
	}
}

算法存在优化空间，可以用二分查找的思路来查找插入位置，但是时间复杂度并没有改变，插入排序在面对倒序排列元素时表现非常糟糕

空间复杂度：$O(1)$

时间复杂度：$O(n²)$

算法稳定性：稳定

希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

  • 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
  • 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录”基本有序”时，再对全体记录进行依次直接插入排序

img

可以说希尔排序也就是插入排序的升级版，代码非常相似，就是在外面加了层嵌套

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void ShellSort(int x[],int n) {
	int temp, j, i,gap;
	for (gap = n/2; gap > 0; gap/=2)   //逐渐减少增量
	{
		for (i = gap; i < n; i++)
		{
			if (x[i] < x[i - gap]) {  //如果x[i]小于前驱
				temp = x[i];              //暂存x[i]
				for (j = i; j > 0 && x[j - gap] > temp; j-=gap)
        //在之前的序列中，找到x[i]的位置，如果x[j-1]<=x[i]了，那么j正好就是插入位置 
				{

					x[j] = x[j - gap]; //大于x[i]的数向后移位
				}
				x[j] = temp;                   //插入
			}
		}
	}
}

空间复杂度：O(1)

时间复杂度：O(n²)

算法稳定性：不稳定

只适用于顺序表

冒泡排序

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢”浮”到数列的顶端。

img

1
2
3
4
5
6
7
8
void BubbleSort(int arr[], int len) {
	int i, j, temp;
	for (i = 0; i < len - 1; i++)   //只用比较n-1次
		for (j = 0; j < len - 1 - i; j++)   //从前往后比，当然从后往前也是可以的
			if (arr[j] > arr[j + 1]) {   //交换
			     swap(arr[j],arr[j+1]);
			}
}

空间复杂度：O(1)

时间复杂度：O(n²)

算法稳定性：稳定

快速排序

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法

img

算法步骤

  1. 从数列中挑出一个元素，称为 “基准”（pivot）;
  2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
  3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int Paritition1(int A[], int low, int high) {
   int pivot = A[low];    //选定low位置上的数作为枢轴，low空缺
   while (low < high) {
     while (low < high && A[high] >= pivot) { 
       --high;                 // 直到找到小于枢轴的数
     }  
     A[low] = A[high];         //把小于枢轴的数换到low的位置去，此时high空缺
     while (low < high && A[low] <= pivot) {
       ++low;                   // 直到找到大于枢轴的数
     }
     A[high] = A[low];        //把大于枢轴的数换到high的位置去，此时low空缺
   }
   A[low] = pivot;            //high=low时结束，此时将枢轴的值放到该中间位置
   return low;
 }

 void QuickSort(int A[], int low, int high) //快排母函数
 {
   if (low < high) {
     int pivot = Paritition1(A, low, high);
     QuickSort(A, low, pivot - 1);   //递归
     QuickSort(A, pivot + 1, high);
   }
 }

空间复杂度：$O(log_2n)到O(n)$，取决于递归树的深度

时间复杂度：最好情况下$O(nlog_2n)$ ，最差情况下$O(n²)$，递归次数是$log_2n$，完成排序操作是n

算法稳定性：不稳定

快速排序在数据已经基本有序的情况下不好发挥其速度，因为会以首个元素为基准，导致其左子表为0，但排序列表为倒序，用快速排序能将其很快变为正序，只要在中间位置选中枢轴即可

选择排序

选择排序是一种简单直观的排序算法，无论什么数据进去都是 $O(n²)$ 的时间复杂度。所以用到它的时候，数据规模越小越好。

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。重复第二步，直到所有元素均排序完毕。

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void swap(int *a,int *b) //交换两个数
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
void selection_sort(int arr[], int len)
{
    int i,j;
        for (i = 0 ; i < len - 1 ; i++)
    {
           int min = i;
           for (j = i + 1; j < len; j++)     //遍历未排序的元素
                  if (arr[j] < arr[min])     //找到目前最小值
                  {                  
                       min = j;    //记录最小值
                       swap(&arr[min], &arr[i]);    //交换
                  }
        }
}

空间复杂度：$O(1)$

时间复杂度：$O(n²)$

算法稳定性：不稳定

堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

  1. 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
  2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

首先需要回忆完全二叉树的顺序存储的性质：

image-20220525162107152

数组0位置是空，然后按层级遍历顺序存储， i的左孩子结点是2i，i的右孩子结点是2i+1，i的父节点是[i/2],而n是数组长度，n/2是最后一个非叶子结点位置

img

先建立大根堆，堆顶元素即是最大元素，然后交换堆顶和堆底元素，将堆顶元素移出堆外，重新构建堆，形成递增序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
void heapify(int* r, int dad, int end) //k~end为调整的范围 
{
	
	int ch = 2 * dad; //ch为dad的左孩子 

	while (ch <= end)
	{
		//让指针j选出左、右孩子中较大者 
		if (ch < end && r[ch] < r[ch + 1]) 
          //"lch<end"表示i还有右孩子 ,若右孩子大，则让指针j指向右孩子// 
		{
			ch++;
		}

//根节点与左、右孩子中的较大者 进行比较，进一步筛选出较大者，并将其换到根节点的位置上去 
		if (r[dad] < r[ch])
		{
			swap(&r[dad], &r[ch]);
		}
		//若发生了，则可能需要对其孩子进行二次调整 
		dad = ch;
		ch = 2 * dad;
	}
}

void heapSort(int r[], int n)
{
	int k;
	//构建堆：由下至上 （由第一个非叶子结点开始） 
	for (k = n / 2; k >= 1; k--)        // n/2即是由下到上的第一个非叶子结点
	{
		heapify(r, k, n);
	}

	//调整堆：由上至下 
	for (k = 1; k < n; k++)
	{
		//移走堆顶元素 
		swap(&r[1], &r[n - k -1]);  
        //r[1]是堆顶元素，即最大的元素，与堆最小的元素进行交换
		//调整堆 
		heapify(r, 1, n - k);        //每次都让堆顶元素出局，再重新构建堆
	}
}

堆的建立：按照完全二叉树的顺序建立堆，然后从底部（表尾）开始，按照堆的要求进行换位，即从下到上，从右到左

堆的插入：新元素放到堆底部（表尾），然后按照堆的要求不断上升，上升只用对比父节点一次关键字

堆的删除：被删除元素和底部元素换位（表尾），然后按堆的要求不断下坠，下坠有可能需要比较两次，也有可能只比一次

注意：堆的排序有两种类型：

  1. 给了数据序列，问变化序列，那就就按堆的建立开始换位
  2. 给了数据序列，强调依次插入，那么就按堆的插入一步步加入形成堆

堆由数组存储，只适合用于排序，而不适合用于查找

空间复杂度：$O(1)$

时间复杂度：$O(nlog_2n)$ 堆顶的交换次数是$n$，堆的调整的时间复杂度是$log_2n$

算法稳定性：不稳定

归并排序

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

算法步骤

  1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
  2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
  3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
  4. 重复步骤 3 直到某一指针达到序列尾；
  5. 将另一序列剩下的所有元素直接复制到合并序列尾。

img

数组的归并操作就是两个有序数组（链表）的合并，就是合并low-mid，mid+1-high两个数组

image-20220526143706541

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void Merge(int a[],int low ,int mid,int high){
  int *b=(int*) malloc(n*sizeof(int));       //创建辅助数组b
    int i,j,k;
    for(k=low;k<=high;k++)                //将数组a复制到数组b中
    {
        b[k]=a[k];   
    }
    i=low;                 //i指向第一组起始位置，j指向第二组
    j=mid+1               //low~mid以及mid+1~high内都是有序的
     for(k=i;i<=mid&&j<=high;k++)   //k是指向数组a起始位置
     {
         if(b[i]<=b[j])     //比较i，j指针数的值，保证稳定性
         {            //结果会替代a[k]位置的值，并且i或者j指针加一，继续比较
           a[k]=b[i];     //直到某一组数都比较完
           i++;
         }else{
           a[k]=b[j];
           j++;
          }
     }     
     while(i<=mid) a[k++]=b[i++];    //将剩下的另一组数填到k后
     while(j<=high) a[k++]=b[j++];
}

void MergeSort(int a[],int low ,int high){
    if(low<high){
        int mid=(low+high)/2;      //从中间划分
        MergeSort(A,low,mid);      //对左半部分进行归并排序
        MergeSort(A,mid+1,high);   //对右半部分进行归并排序
        Merge(A,low,mid,high);     //归并
    }
}

空间复杂度：$O(n)$ 来自辅助数组

时间复杂度：$O(nlog_2n)$ 归并次数是$log_2n$，每次归并的时间复杂度是$n$

算法稳定性：稳定

基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数

img

假设要比较很多两位整数的大小，首先需要建立队列，第一趟先比较各个数个位大小，个位大的先入队，然后出队，按十位大的先入队，十位相同的两个数，由于第一趟排序后，个位大的排在前面，所以个位大的先入队，当数都入队后，再出队

一般使用链式队列来存储数据，需要r个队列，r为进制位数

空间复杂度：O(r)

时间复杂度：O(d(n+r)) 一次排序需要O(r)，总共有d次分配，收集

稳定性：稳定

外部排序

由于数据元素过多，无法一次全部读入内存进行排序，所以需要在内存和磁盘之间进行操作

外部排序的核心还是归并排序，在内存中最少只需要3块大小的缓冲区就能对任意大小的文件进行排序归并

image-20220526160856370

每次读入两块数据到缓冲区，然后进行归并排序，结果到输出缓冲区写入到磁盘中去，如果输入缓冲区空了就再加入一块新数据

步骤：

  1. 生成r个初始归并段
  2. 进行S趟k路归并 $S=[log_kr]$

外部排序时间开销=读写外存的时间+内部排序所需时间+内部归并所需时间

优化思路：

  1. 可以多加2个缓冲区，这样就是4路归并，减少读写磁盘的时间（败者树）
  2. 减少初始归并段（置换-选择排序）

败者树

多加了缓冲区后，内部排序需要对比关键字的次数也增加了，为了减少内部排序的对比次数，可以采用败者树的形式

image-20220526163640881

接下来的对比，只需要对比分支结点里面记录的败者归并段的首元素就行了，只需要对比关键字$log_2k$次

置换-选择排序

image-20220526164455552

将初始待排序文件集中放在一起，然后进入内存工作区，内部排序得到最小的值，输出该元素，并记录该元素的值为MIN，添加新元素，每次离开内存工作区的元素要比MIN大，并且会成为新的MIN

如果工作区所有的数都比MIN小，就新开一个归并段

最佳归并树

在进行归并的时候，将每个初始归并段看做一个叶子结点，归并段的长度作为结点权值，那么利用哈夫曼树的性质就能实现最少归并次数

image-20220526165915036

归并过程中磁盘I/O次数=归并树WPL×2

对于K叉归并，如果初始归并段的数量无法构成严格的k叉归并树，就需要补充几个长度为0的虚段，至于虚段的计算，参照二叉树的性质

已知树的结点数=总度数+1 即$n=n_1+2n_2+1$，同时$n=n_0+n_1+n_2$，所以可以推出$n_0=n_2+1$

补充了虚段的最佳归并树的结点只有两种类型，叶子结点和度为k的结点，叶子结点由归并段结点和虚段结点组成，那么可根据树的性质推导

  • $1+k×n_k=n$ 即 1+树的总度数=树的结点总数

  • $n_0+n_k=n$ 即 叶子结点+度为k的结点=树的结点总数

  • $n_0=n_v+n_s$ 即 叶子结点=虚段结点+归并段结点

根据这三个公式推出：$n_v+n_s+n_k=1+k×n_k$，

即$n_k=\frac{(n_v+n_s-1)}{k-1}$

为了让$n_k$为正整数，需要补充的虚段就是满足这一条件的最小正整数