《数据结构》排序

插入排序

直接插入排序

原理
- 某节点前是排好序的，节点后是未排序的，未排序数据从后向前一一比较大小并交换数据，边比较边移动元素
平均复杂度
- $O(n^2)$
稳定性
- 稳定
例图
代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


void insertion_sort(int arr[],int len)
{
    int i,j,key;
    for(i = 1;i<len;i++)
    {
        key = arr[i];
        j = i -1;
        while((j>=0)&& (arr[j] > key))
        {
            arr[j+1] = arr[j];//把大的数值往右换
            j--;
        }
        arr[j+1] = key;//把小的数值往左换
    }
}

希尔排序

原理
- 先将整个待排序的记录序列按增量分割成若干子序列，每个子序列分别进行直接插入排序，然后不断减小增量的大小，直到序列有序
平均复杂度
- $O(n\log_2n)$
稳定性
- 不稳定
常考点
- 计算希尔排序的增量大小
例图
代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


void shell_sort(int arr[],int len)
{
    int gap,i,j;
    int temp;
    for(gap = len>> 1; gap >0;gap >>=1)
    {
        for (i = gap; i <len; i++)
        {
            temp = arr[i];
            for (j = i -gap;j>=0 && arr[j] > temp; j-= gap)
            {
                arr[j + gap] = arr[j];
            }
            arr[j+gap] = temp;
        }
    }
}

折半插入排序

原理
- 先折半查找出元素的待插入位置，然后统一地移动待插入位置后的所有元素
时间复杂度
- $O(n^2)$
稳定性
- 稳定
常考点
- 折半插入排序的总趟数 = 直接插入排序的总趟数 = n - 1
- 折半插入排序元素的移动次数 = 元素的移动次数
- 折半插入排序使用辅助空间的数量 = 直接插入排序辅助空间使用量
- 与直接插入排序相比两者元素之间的比较次数不同

交换排序

冒泡排序

原理
- 比较相邻的元素，如果第一个比第二个大，就交换它们两个
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对
- 上一步做完后，最后的元素会是最大的数
- 针对所有的元素重复以上的步骤，除了最后一个
- 直到没有任何一对数字需要比较
平均复杂度
- $O(n^2)$
稳定性
- 稳定
常考点
- 每一趟最后一个元素都是最大的元素（从小到大的序列）
- 元素从小到大时 = 最坏情况比较次数 = $\frac{n\times(n-1)}{2}$
- 元素从小到大时 = 最好情况比较次数 = n-1
例图

代码

 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


#include <stdio.h>
void bubble_sort(int arr[],int len)
{
  int i,j,temp;
  for(i = 0;i<len-1;i++)
  {
    for (j = 0;j< len-1-i;j++)
    {
      if(arr[j] > arr[j+1])
      {
        temp = arr[j];
        arr[j] = arr[j+1];
        arr[j + 1] = temp;
      }
    }
  }
}
int main()
{
  int arr[] = {22,34,3,32,82,55,89,50,37,5,64,35,9,70};
  int len = (int)sizeof(arr)/sizeof(*arr);
  bubble_sort(arr,len);
  int i;
  for(i = 0;i<len;i++)
  {
    printf("%d",arr[i]);
  }
  return 0;
}

快速排序

原理
- 通过一趟排序将要排序的数据分割成独立的两部分
- 其中一部分的所有数据都比另外一部分的所有数据都要小
- 然后再按此方法对这两部分数据分别进行快速排序
- 整个排序过程可以递归进行，以此达到整个数据变成有序序列
平均时间复杂度
- $O(n\log_n)$
稳定性
- 稳定
常考点
- 蕴含了分而治之的思想
- 就平均性能而言，是目前最好的内部排序方法
- 当数据随机或数据量很大的时候，适合快速排序；当排序的数据已经基本有序，不适合快速排序
- 每次的枢纽值把表分为等长的部分时，速度最快
- 快速排序每趟都把基准元素放在最终位置（常用于计算是不是某一趟排序结果的题目，如第一趟至少有1个元素在最终位置，第二趟至少2个）
- 最大递归深度 = 枢纽值每次都将子表等分 = 树高位$\log_2n$
- 最小递归深度 = 枢纽值每次都是子表的最大值或最小值 = 单链表 = 树高为n
例图
- 三位取中【通常取最左边的元素为枢纽值】
- 根据枢纽值进行分割【通常先从右到左交换比枢纽值小的，再从左到右交换比枢纽值大的
代码

 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


void Qsort(int A[],L,R)//a数组保存数据，L和R是边界
{
  if(L>=R)//当前区间元素个数<=1则退出
  {
    return;
  }
  int key,i = L,j = R;//i和j是左右两个数组下标移动
  把A[L~R]中随机一个元素和A[L]交换//快排优化，使得基准值的选取随机
  key = A[L];//key作为枢值参与比较
  while(i<j)
  {
    while(i<j && A[j] > key)
    {
      j--;
    }
    while(i<j && A[i] < = key)
    {
      i++;
    }
    if(i < j)
    {
      swap(A[i],A[j]);//交换A[i]和A[j]
    }
  }
  swap(A[L],A[i]);
  Qsort(A,L,i-1);//递归处理左区间
  Qsort(A,i+1,R);//递归处理右区间

}

选择排序

简单选择排序

原理
- 每一趟从待排序的数据元素中选择最小或最大的一个元素作为首元素，直到所有元素排序完毕为止
平均复杂度
- $O(n^2)$
稳定性
- 不稳定
常考点
- 比较次数数量级与序列初始状态无关
例图
代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


void selectSort(vector<int>& nums,int n)
{
    for(int i = 0; i < n;i++)
    {
        int min = i;

    
        for(int j = i+1;i < n;j++)//遍历取得最小值
        {
            if(nums[j] < nums[min])
            {
                min = j;
            }
        }
        if(min != i) //移动到末尾
        {
            int tmp = nums[i];
            nums[i] = nums[min];
            nums[min] = tmp;
        }
    }
}

堆排序

原理
- 堆是具有特殊性质的完全二叉树
- 大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]【根最大】
- 小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] 【根最小】
- 堆的基本思想
  - 将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆
  - 将堆顶元素与末尾元素交换，将最大元素沉到数组末端
  - 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素
  - 反复执行调整+交换步骤，直到整个序列有序
平均时间复杂度
- $O(n\logn)$
稳定性
- 不稳定
常考点
- 取一大堆数据中的k个最大或最小的元素时，都优先采用堆排序
- 堆排序的序列相当于二叉树的层次序列
- 可将堆视作一棵完全二叉树，采用顺序存储方式保护堆
- 插入和删除一个新元素的时间复杂度都为$O(\log_2n)$
- 构造n个记录的初始堆，时间复杂度为O(n)
代码

 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


void buildMaxHeap(int A[],int n)
{
    for(int i =n/2-1;i >= 0;i--)
    {
        maxHeapIfy(A,i,n);
    }
}

void maxHeapIfy(int A[],int i,int n)
{
    int l = 2 * i + 1;

    int r = 2 * i + 1;

    int largest = i;

    if(l<n && A[l]>A[largest])
    {
        largest = l ;
    }
    if(l<n && A[r]>A[largest])
    {
        largest = r ;
    }
    if(largest != i)
    {
        swap(A[i],A[largest]);
        maxHeapIfy(A,largest,n);
    }
}

void heapSort(int A[],int n)
{
    buildMaxHeap(A,n);
    for(int i = n-1;i> 0 ;i--)
    {
        swap(A[0],A[i]);
        maxHeapIfy(A,0,i);
    }
}

建堆过程

堆增加一个元素的过程

掌握大顶堆和小顶堆的概念

归并排序和基数排序

归并排序

原理
- 利用归并的思想实现的排序方法
- 该算法采用经典的分治策略
- 分治法将问题分成一些小的问题然后递归求解
- 治的阶段则将分的阶段得到的各答案修补在一起
平均复杂度
- $O(n\logn)$
稳定性
- 稳定
常考点
- 分阶段可以理解为递归拆分子序列的过程，递归深度为$\log_2n$
- 空间复杂度为O(n)
- 比较次数数量级与序列初始状态无关
- 对于N个元素进行k路归并排序的趟数满足$k^m = N$
例图
代码

 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 merge(vector<int>& arr,int l,int mid,int r)
{
    int index = 0 ;
    int ptrL = l;
    int ptrR = mid;
    static vector<int>tempary;
    if(arr.size() > tempary.size())
    {
        tempary.resize(arr.size());//更新缓存数组长度
    }
    while(ptrL ! = mid && ptrR ! = r)
    {
        if(arr[ptrL] < arr[ptrR])//比较左右分组后数组长度
        {
            tempary[index++] = arr[ptrL++];
        }
        else
        {
            tempary[index++] = arr[ptrR++];
        }
    }
    while(ptrL ! = mid)
    {
        tempary[index++] = arr[ptrL++];
    }
    while(ptrR ! = r)
    {
        tempary[index++] = arr[ptrR++];
    }
    copy(tempary.begin(),tempary.begin()+index,arr.begin()+l)

}

void mergeSort(vector<int>& arr,int l,int r)
{
    if(r - l <= 1>)
    {
        return;
    }
    int mid = ( l + r ) / 2;
    mergeSort(arr,l,mid);
    mergeSort(arr,mid,r);//递归排序
    merge(arr,l,mid,r);//合并数组
}

基数排序

原理
- 将整数按位分割成不同的数字，然后按每个位数分别比较
平均时间复杂度
- $O(N*K)$
稳定性
- 稳定，外部排序
常考点
- 通常基数排序第一趟按照个位数字大小，第二趟按照十位数字大小
- MSD是最高位优先，LSD是最低位优先
- 基数排序不能对float和double类型的实数进行排序
例题
代码

 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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61


int maxbit(int data[],int n)
{
    int maxData = data[0];

    for(int i = 1;i< n;++i)
    {
        if(maxData < data[i])
        {
            maxData = data[i];
        }
    }
    int d = 1;
    int p = 10;
    while (maxDate >= p )
    {
        maxData /= 10;
        ++d;
    }
    return d;

}

void radixSort(int data[],int n)
{
    int d = maxbit(data,n);
    int *tmp = new int[n];
    int *count = new int[n];
    int i,j,k;
    int radix = 1;
    for(i = 1;i <= d;i++)
    {
        for(j = 0;j < 10;j++)
        {
            count[j] = 0;
        }
        for(j = 0;j < n;j++)
        {
            k = (data[j]/radix) % 10;
            count[k]++;
        }
        for(j = 1;j < 10;j++)
        {
            count[j] = count[j-1]+count[j];

        }
        for(j = n-1;j>= 0 ;j--)
        {
            k = (data[j]/radix) % 10;
            tmp[count[k] - 1] = data[j];
            count[k]--;
        }
        for(j = 0;j < n;j++)
        {
            data[j] = tmp[j];
            
        }
        radix = radix * 10;
    }
    delete []tmp;
    delete []count;
}

外部排序

概念
- 当待排序的文件比内存的可使用容量还大时，文件无法一次性放到内存中进行排序
- 需要借助外部存储器，此时需要用到外部排序算法
原理
- 按照内存大小，将大文件分成若干长度为i的子文件（i应当小于内存的可使用量）
- 然后将各个子文件依次读入内存，使用适当的内部排序算法对其进行排序，完成排序的子文件统称为归并段或顺段
- 将排好序的归并段重新写入外存，为下一个子文件排序腾出内存空间
- 对得到的顺段进行合并，直到得到整个有序的文件为止
举例
- 有一个含有10000个记录的文件，但是内存可使用量仅为1000个记录，需要使用外部排序算法
  - 将整个文件等分为10个临时文件（每个文件有1000个记录）
  - 然后将这10个文件依次进入内存，采取适当的内存排序算法对其中的记录进行排序，将得到的有序文件（初始归并段）移至内存
  - 对得到的10个初始归并段进行如图的两两归并，直到得到一个完整的有序文件
  - 如图有10个初始归并段到一个有序文件，共进行了4次归并，每次都由m个归并段得到[m/2]个归并段，这种归并方式被称为2-路平衡归并
效率分析
- 影响整体排序效率的因素主要取决于读写外存的次数，即访问外存的次数越多，算法花费的时间越多，效率就越低
- 对于同一文件来说，对其进行外部排序时访问外存的次数同归并的次数成正比，即归并操作的次数越多，访问外存的次数就越多
- 提高效率的方法
  - 增加k-路平衡归并中的k值
  - 尽量减少初始归并段的数量m，即增加每个归并段的容量
常用公式
- 对于具有m个初始归并段进行k-路平衡归并时，归并的次数为$s = \lfloor \logk m \rfloor$(s表示归并次数)

败者树

对于k路归并，第一次构造序对比关键字k-1次，选出最小元素需要对比关键字$\lceil \log_2k \rceil$

归并树

归并过程的磁盘IO次数 = 归并树WPL *2
初始归并段数量无法构成严格k叉归并树的情况下需要补充长度为0虚段再进行哈夫曼树构造
- 设度为k的结点为$n_k$个，度为0的结点为$n_0$个，归并树总结点数 = n
- 初始归并段数 + 虚段数量 = $n_0$
- $n_k = \frac{n_0-1}{k-1}$
- (初始归并段数 - 1)% (k-1) = 0,不需要补充
- (初始归并段数 - 1)%(k-1) = u $\neq$ 0,虚补充(k-1) - u个虚段