排序

技术探索
🗨️字数统计=3.7k字 ⏳阅读时长≈15分钟

总览


一、插入排序 O(n^2)

1. 直接插入排序 稳定

算法思想：

边查边移：

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

算法图解：

img

具体代码：

1
2
3
4
5
6
7
8
9
10
11
12
template <class T>
void Sort(T a[], int n){ //n表示数组长度
    int i,j;
    for(i = 1;i<n;i++){
        if(a[i]<a[i-1]){
            T temp = a[i]; 
            for(j = i-1; a[j]>temp && j>=0; j--)
                a[j+1] = a[j]; //元素后移
            a[j+1] = temp; //插入
        }
    }
}

算法分析：

  • 平均时间复杂度：O(n^2)
  • 最好情况(有序) O(n)
  • 最坏情况(逆序) O(n^2)
  • 稳定性：稳定

2. 折半插入排序 稳定

算法思想：

先查后移：

将直接插入排序中寻找A[i]的插入位置的方法改为采用折半比较，即可得到折半插入排序算法，

仅仅减少了查找排序的比较次数，约为O(nlog2n)，元素的移动次数并未改变，依赖于排序表的初始状态

具体代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void Sort(int a[], int n){ //n表示数组长度
    int i,j,temp;
    int low,high,mid;
    for(i = 1;i<n;i++){ //以第一个数a[0]为基准比较
        temp = a[i];
        low = 0;high = i-1;
        //查找
        while(low<=high){
            mid = (low+high)/2;
            if(a[mid]>temp) high = mid-1;
            else low = mid+1;
        }
        //后移
        for(j = i-1;j>=high+1;j--)
            a[j+1] = a[j];
        a[high+1] = temp;
    }
}

算法分析：

  • 平均时间复杂度：O(n^2)
  • 稳定性：稳定

3. 希尔排序 不稳定

算法思想：

又称“缩小增量排序”

把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；

随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

数组长度10

则增量序列一般为：5，3，1

算法图解：

img

具体代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Sort(int a[], int n){ //n表示数组长度
    int i, j, dk, temp;
    for (dk = n / 2; dk >= 1; dk = dk / 2){
        //步长为dk的直接插入排序
        for (i = dk + 1; i < n; i++){ 
            if(a[i-dk]>a[i]){
                temp = a[i];
                for (j=i-dk; a[j]>temp && j>=0; j=j-dk)
                    a[j + dk] = a[j];
                a[j + dk] = temp;
            } //if
        }
    }
}

二、交换排序

1. 快速排序 O(nlog2n) 不稳定

算法思想：

  • 从数列中挑出一个元素，称为 “基准”（pivot）（一般选取数列的第一个元素作为基准）；
  • 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
  • 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

算法图解：

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
void QuickSort(int A[], int low, int high)
{
    if (low < high)
    {
        int pivots = Partition(A, low, high);
        QuickSort(A, low, pivots);
        QuickSort(A, pivots + 1, high);
    }
}
//划分算法
int Partition(int A[], int low, int high)
{
    int pivots = A[low];
    while (low < high)
    {
        //从后往前找比中轴值小的元素，若找到，则交换
        // 一定要先从后往前查找，再从前往后
        while (low < high && A[high] >= pivots)
            high--;
        A[low] = A[high];
        //从前往后找比中轴值大的元素,若找到,则交换
        while (low < high && A[low] <= pivots)
            low++;
        A[high] = A[low];
    }
    A[low] = pivots;
    return low;
}

算法分析

  • 最好(划分平衡)：O(nlogn)
  • 最坏(有序)：O(n2)

假如给定15个数，求快速排序的最多、最少比较次数

img

2. 冒泡排序 O(n^2) 稳定

算法思想：

从后往前（从前往后）两两比较相邻的元素，若为逆序，则交换，直到序列比较完，称为一趟冒泡。

下一趟冒泡时，前一趟确定的最小元素不再参与比较，待排序列减少一个元素。

这个算法的名字由来是因为越小（大）的元素会经由交换慢慢“浮”到数列的顶端，故名。

算法图解：

img

具体代码：

1
2
3
4
5
6
7
8
9
10
11
12
void sort(int a[], const int size)
{
    for (int i = 0; i < size - 1; i++){
        for (int j = 0; j < size; j++){
            if (a[j] > a[j + 1]){
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
    }
}

算法改进1：

在第一遍排序后，最大值必定在数组最大编号的元素中；第二遍排序后，最大的两个值都在最终位置了，依次类推。所以，修改这个冒泡排序法（假设数组中有10个元素），使得在第二遍排序时比较8次，在第三遍排序时比较7次，而不是每次排序时都比较9次

1
2
3
4
5
6
7
8
9
10
11
void sort2(int a[], const int size){
    for(int i = 0; i < size-1; i++){
        for(int j = 0;j<size-i-1;j++){
            if(a[j]>a[j+1]){
                int temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
            }
        }
    }
}

算法改进2：

如果某趟冒泡排序没有发生交换，即说明数组中的元素已经全部有序，此时无需再进行排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void sort3(int a[], const int size)
{
    for (int i = 0; i < size - 1; i++){
        int ifSwap = false;
        for (int j = 0; j < size - i - 1; j++){
            if (a[j] > a[j + 1]){
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
                ifSwap = true;
            }
        }
        if(ifSwap == false)
            break;
    }
}

算法分析：

  • 平均时间复杂度：O(n2)
  • 最好情况(有序) O(n)
  • 最坏情况(逆序) O(n2)
  • 稳定性：稳定（全局有序的）

三、选择排序 不稳定

1. 简单选择排序 O(n^2)

算法思想：

每次排序都从未排序列选取最小元素放在第 i 个位置，第 i 次排序即从 i~n 中挑选最小元素与 A[i] 交换，一共循环 n-1 次

算法图解：

img

具体代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template<class T> 
void SortTwo(T *a, int len){
    int min; //记录最小值下标
    for(int i = 0;i<len-1;i++){
        min = i; //设置最小值
        for(int j = i+1; j<len; j++){
            if(a[min]>a[j])
                min = j;
        }
        //更新最小值
        if(min != i){
            T temp = a[min];
            a[min] =a[i];
            a[i] = temp;
        }      
    }
}

算法分析：

选择排序是最稳定的排序算法之一，因为无论什么数据进去都是O(n²)的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间。

元素间比较的次数与序列的初始状态无关

2. 堆排序 O(nlog2n)

算法思想：

  • a.将无序的序列构建成一个堆，根据升序降序需求选择大根堆或小根堆;（先找n/2[取下整]的分支结点，即最后一个分支结点，调整该结点和他的孩子结点，然后依次从下往上对结点数-1的结点进行调整，最后再从上往下调整检查一遍）
  • b.将堆顶元素与末尾元素交换，将最大元素”沉”到数组末端;
  • c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

算法图解：

img img

img

img

来个动图直观感受一下：

img

算法分析：

时间复杂度始终为O(nlog2n)

稳定性：不稳定


四、归并排序 O(nlog2n) 稳定

算法思想：

归并的含义是将两个或以上的有序表组合成一个新的有序表；

以二路归并为例：两两归并，Merge()的功能是将前后相邻的两个有序表归并为一个有序表；

递归形式的二路归并是基于分治算法的；

算法图解：

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
int *B = (int *)malloc(sizeof(int) * (n + 1)); //动态分配辅助数组B
void Merge(int A[], int low, int mid, int high)
{
    for (int k = low; k <= high; k++)
        B[k] = A[k]; //将A中所有元素复制到B中
                     //对B两个部分依次比较，选取最小值放入A
    for (i = low, j = mid + 1, k = i; i < mid && j <= high; k++)
    {
        if (B[j] <= B[i])
            A[k] = B[i++];
        else
            A[k] = B[j++];
    }
    while (i <= mid) //若第一个表未检测完
        A[k++] = B[i++];
    whle(j <= high) //若第二个表未检测完
        A[k++] = B[j++];
}
void MergeSort(int A[], int low, int high)
{
    int mid = (low + high) / 2;  //从中间划分两个子序列
    MergeSort(A, low, mid);      //对左侧序列进行递归排序
    MergeSort(A, mid + 1, high); //对右侧序列进行递归排序
    Merge(A, low, mid, high);    //归并
}

算法分析：

和选择排序一样，归并排序不受输入数据的影响，时间复杂度始终是 O(nlog2n)

稳定性：稳定


五、基数排序 稳定

算法思想：

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。

由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

算法图解：

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
45
46
47
48
49
50
51
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 (maxData >= p)
    {
        //p *= 10; // Maybe overflow
        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[10]; //计数器
    int i, j, k;
    int radix = 1;
    for(i = 1; i <= d; i++) //进行d次排序
    {
        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]; //将tmp中的位置依次分配给每个桶
        for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
        {
            k = (data[j] / radix) % 10;
            tmp[count[k] - 1] = data[j];
            count[k]--;
        }
        for(j = 0; j < n; j++) //将临时数组的内容复制到data中
            data[j] = tmp[j];
        radix = radix * 10;
    }
    delete []tmp;
    delete []count;
}

六、排序的相关算法

1. 编写算法使之能在数组[1….n]中找出第K小的元素

算法思想：利用快速排序的划分操作 确定pivot ，a[low] = pivot。

  • 若low==k,则返回a[low];

  • 若low>k,则递归查找low左边数组第k个元素；

  • 若low<k，则递归查找low右边数组第k-low个元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int elem_k(int a[], int low, int high, int k){
      int pivot = A[low];
      //由于下面划分会修改low和high的值，递归的时候又需要用到他们，所以先存储起来
      int low_temp = low; 
      int high_temp = high;
      //下面即为快速排序的划分算法
      while(low < high){
            while(A[low] < pivot)
              low++;
            A[low] = A[high];
            while(A[high] > pivot)
              high--;
            A[high] = A[low];
      }
      A[low] = pivot;

      if(low = k)
        return A[low];
      else if(low > k)
        return elem_k(a,low_temp,low-1,k);
      else
        return elem_k(a,low+1,high_temp,k-low);
}

2. 有一个仅由红，白，蓝三个颜色组成的条块序列，设计算法将红色全都排在前面，蓝色全都排在后面（荷兰国旗）

算法思想：设置三个指针i，j，k，j为工作指针，顺序扫描线性表，将红色序列全都放在i指针之前，将蓝色序列全都放在k指针之后。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef enum{Red,White,Blue};
void FlagArrange(color a[], int n){
  int i = 0, j = 0, k = n-1;
  while(j < k)
        switch(a[j]){
          case Red: 
            swap(A[i],A[j]);
            j ++;
            i ++;
            break;
          case White:
            j ++;
            break;
          case Blue:
            swap(A[j],A[k]);
            k --; 
            //此处没有j++是为了防止交换后的颜色任为蓝色
    }
}

case Red无须考虑交换后是否仍为红色，因为i指针后移还会遍历到该条块；

而case Blue需要考虑交换后是否为蓝色，因为k指针递减遍历不到该结点就会因为j>k而退出循环

3. 双向冒泡算法

算法思想：在正反两个反向交替进行扫描，

即第一趟把关键字最大的元素放在序列的最后面，第二趟把关键字最小的元素放在序列的最前面，如此反复进行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void BubbleSort(Element A[], int n){
  	int low = 0, high = n-1;
  	bool flag = true;
  	while(low < high && flag){
        flag = false;
        for(int i=low; i<high; i++){ //奇数次从前向后气泡最大值
          if(A[i+1]<A[i]){
            swap(A[i],A[i+1]);
            flag = true;
        }
    }
    high --; //修改上界
	for(int j=high; j>low; j--){ //偶数次从后向前气泡最小值
          if(A[j] < A[j-1]){
            swap(A[j],A[j-1]);
            flag = true;
          }
    }
    low ++; //修改下界
  }
}

4. 已知线性表按顺序存储，且每个元素都是不相同的整数型元素，设计把所有的奇数移动到偶数前边的算法

算法思想：类比快速的排序的划分算法，使用交换的理念，从前往后找偶数，从后往前找奇数，找到后两者互换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void move(ElemType A[], int len){
      int low = 0;
      int high = len-1;
      while(low<high){
            while(low<high && A[low]%2!=0)
               low ++;
            while(low<high && A[high]%2=0) 
               high --;
            if(low<high)
               swap(A[low],A[high]); //交换
            low ++;
            high --;
      }
}

5. 若只想得到一个序列中第k(k>=5)个最小元素之前的部分排序序列，则最好采用什么排序方法

最好采用堆排序。

  • 插入排序（直接插入，折半插入，希尔排序），快速排序和归并排序只有在元素全部排完序之后，才能得到所有元素的有序序列。

    冒泡排序，简单选择排序和堆排序每趟排序后都能确定一个部分有序序列。

  • 对于堆排序，有n个元素的序列，建立初始堆的时间不超过4n,取得第k个最小元素之前的排序序列所花的时间为klog2n，总时间为4n+klog2n；

    对于冒牌排序和简单选择排序，完成此功能所花时间为kn（k>=5)

分享到