排序算法

发表于 分类于 Waline： 本文字数： 13k 阅读时长 ≈ 12 分钟

前言

排序算法是使一组无序的序列按照某种从小到大或从大到小的顺序输出的过程，主要分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存，一般说的常用排序均是内部排序。

常用排序算法

常用排序算法分类

常用排序算法根据排序的原理方法一般分为：

  1. 交换排序
    交换排序包括冒泡排序和快速排序
  2. 选择排序
    选择排序包括简单选择排序和堆排序
  3. 插入排序
    插入排序包括直接插入排序和希尔排序
  4. 归并排序
  5. 基数排序

常用排序算法时间空间复杂度及稳定性总结

排序方法 平均时间复杂度 最坏情况 最好情况 空间复杂度 稳定性
冒泡排序 O(n²) O(n²) O(n) O(1) 稳定
快速排序 O(nlog2n) O(n²) O(nlog2n) O(nlog2n) 不稳定
简单选择排序 O(n²) O(n²) O(n²) O(1) 不稳定
堆排序 O(nlog2n) O(nlog2n) O(nlog2n) O(1) 不稳定
直接插入排序 O(n²) O(n²) O(n) O(1) 稳定
希尔排序 O(nlog2n) O(nlog2n) —— O(1) 不稳定
归并排序 O(nlog2n) O(nlog2n) O(nlog2n) O(n) 稳定
基数排序 O(d(n+r)) O(d(n+r)) O(d(n+r)) O(n+r) 稳定

冒泡排序

冒泡排序

思路

令数组长度为n
1.比较相邻的前后2个数据，如果前面数据大于后面的数据，就将二个数据交换
2.对数组的第0个数据到n-1个数据进行一次遍历后，最大的一个数据就“沉”到数组第n-1个位置
3.令n=n-1，如果n不为0就重复前面二步，否则排序完成

代码实现

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
// 交换两个数
void mySwap(int &a, int &b)
{
    int tmp = a;
    a = b;
    b = tmp;
}

// 打印长度为len的数组a[]第loop趟排序结果
void myPrint(int a[], int len, int loop)
{
    std::cout << "loop[" << loop << "]: ";
    for (int i = 0; i < len; i++)
    {
        std::cout << a[i] << " ";
    }
    std::cout << std::endl;
}

/* 冒泡排序*/
void bubbleSort(int a[], int len)
{
    for (int i = 0; i < len; i++)
    {
        for (int j = 0; j < len-i-1; j++)
        {
            if (a[j] > a[j+1])
            {
                mySwap(a[j], a[j+1]);
            }
        }
        myPrint(a, len, i);
    }
}

冒泡排序改进1

思路

对冒泡排序常见的改进方法是加入一标志性变量isExitExchange，用于标志某一趟排序过程中是否有数据交换，如果进行某一趟排序时并没有进行数据交换，则说明数据已经按要求排列好，可立即结束排序，避免不必要的比较过程

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/* 改进的冒泡排序1
增加某一趟是否有交换的记录，没有则认为已经排序完成，否则没有排序完成，继续交换
*/
void bubbleSortByIsExistExchange(int a[], int len)
{
    bool isExitExchange = true; // 第一次假定存在交换
    int tmpLen = len-1; //若存在交换，下一次for循环遍历的长度,
                        //初始化为len-1,因为for循环从0开始，且数组索引有i+1
    while (isExitExchange)  
    {
        isExitExchange = false; //默认是不存在交换

        for (int i = 0; i < tmpLen; i++) 
        {
            if (a[i] > a[i+1])
            {
                mySwap(a[i], a[i+1]);
                isExitExchange = true;
            }
        }
        myPrint(a, len);
        tmpLen--;
    }
}

冒泡排序改进2

思路

进一步的，可以增加记录某一趟遍历最后一次交换的位置，下一次从头开始遍历的时候就可以从记录的位置索引为长度开始跳跃着交换，而不需要每次长度只递减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
/*改进的冒泡排序2
增加记录某一趟遍历最后一次交换的位置，下一次从头开始遍历的时候就可以从记录的位置索引为长度开始跳跃着交换，而不需要每次长度只递减1
*/

void bubbleSortByRecordLastSwapIndex(int a[], int len)
{
    int lastSwapInex = len - 1; //若存在交换，下一次for循环遍历的长度,初始化为len-1
    int swapFlag = lastSwapInex; //swapFlag: 是否继续交换的标志

    while (swapFlag)
    {
        lastSwapInex = swapFlag; // 根据上一次记录的最后交换索引，更新本次for循环的长度
        swapFlag = 0;  // 默认是0，不继续
        for (int i = 0; i < lastSwapInex; i++)
        {
            if (a[i] > a[i+1])
            {
                mySwap(a[i], a[i+1]);
                swapFlag = i;
            }
        }   
        myPrint(a, len);
    }
}

冒泡排序结果打印

before sorted print:
loop[0]: 1 6 8 9 4 5 6 25 19 3 0 2
sorted process print:
loop[0]: 1 6 8 4 5 6 9 19 3 0 2 25
loop[1]: 1 6 4 5 6 8 9 3 0 2 19 25
loop[2]: 1 4 5 6 6 8 3 0 2 9 19 25
loop[3]: 1 4 5 6 6 3 0 2 8 9 19 25
loop[4]: 1 4 5 6 3 0 2 6 8 9 19 25
loop[5]: 1 4 5 3 0 2 6 6 8 9 19 25
loop[6]: 1 4 3 0 2 5 6 6 8 9 19 25
loop[7]: 1 3 0 2 4 5 6 6 8 9 19 25
loop[8]: 1 0 2 3 4 5 6 6 8 9 19 25
loop[9]: 0 1 2 3 4 5 6 6 8 9 19 25
loop[10]: 0 1 2 3 4 5 6 6 8 9 19 25
loop[11]: 0 1 2 3 4 5 6 6 8 9 19 25
after sorted print:
loop[0]: 0 1 2 3 4 5 6 6 8 9 19 25

快速排序

思路

思想是分治 和递归

  1. 确定基准值(一般是序列第一个位置、最后一个位置或中间位置)
  2. 从序列后面开始向前找元素，若小于基准值则交换之，否则继续前向步进，直到找到一个满足条件的值
  3. 从序列前面开始向后找元素，若大于基准值则交换之(元素与上一次的交换操作的结果进行交换)，否则继续向后步进，直到找到一个满足条件的值；
  4. 重复2~3操作，直到基准值左边的元素均不大于基准值，基准值右边的元素均不小于基准值，分为了左半部分和右半部分
  5. 分别对左半部分和右半部分重复1~4的操作

代码实现

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
/*进行经过1~4步操作,并返回基准值的位置*/
int getPartionIndex(int a[], int left, int right)
{
    int stardardValue = a[left]; // 初始化基准值为序列第一个位置的值
    int i = left; // 初始i,j
    int j = right;

    while (i < j) // 循环继续条件
    {
        while ((i < j) && (a[j] >= stardardValue)) //从后面元素开始向前遍历，未找到满足条件继续步进
        {
            j--;
        }
        mySwap(a[i], a[j]);  //找到了一个小于stardardValue，则交换

        while ((i < j) && (a[i] <= stardardValue)) //从前面元素开始向后遍历，未找到满足条件继续步进
        {
            i++;
        }
        mySwap(a[i], a[j]); //找到了一个大于stardardValue，则交换
    }
    myPrint(a, right, i);
    return i;
}

// 快速排序
void quickSort(int a[], int left, int right)
{
    if (left < right) // 递归终止条件
    { 
       //获取基准位置，使基准位置左边数不比基准大，右边数不比基准小
        int stardardValueIndex = getPartionIndex(a, left, right); 
        quickSort(a, left, stardardValueIndex - 1); // 快排左边的部分
        quickSort(a, stardardValueIndex + 1, right); // 快排右边的部分
    }
}

快速排序结果打印

before sorted print:
loop[0]: 1 6 8 9 4 5 6 25 19 3 0 2
sorted process print:
loop[1]: 0 1 8 9 4 5 6 25 19 3 6
loop[8]: 0 1 2 6 4 5 6 3 8 19 25
loop[2]: 0 1 2 6 4 5 6
loop[7]: 0 1 2 3 4 5 6
loop[3]: 0 1 2 3 4 5
loop[4]: 0 1 2 3 4 5
loop[5]: 0 1 2 3 4 5
loop[10]: 0 1 2 3 4 5 6 6 8 9 19
after sorted print:
loop[0]: 0 1 2 3 4 5 6 6 8 9 19 25

简单选择排序

简单选择排序

思路

直接选择排序和直接插入排序类似，都将数据分为有序区和无序区，所不同的是直接播放排序是将无序区的第一个元素直接插入到有序区以形成一个更大的有序区，而直接选择排序是从无序区选一个最小的元素直接放到有序区的最后

  1. 初始时，数组全为无序区为a[0~n-1]
  2. 在无序区a[in-1]中选取一个最小的元素，将其与a[i]交换。交换之后a[0i]就形成了一个有序区
  3. i++并重复第二步直到i—>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
30
31
32
33
//获取长度为len的序列a[] 从索引index开始到len-1范围序列的最小值的索引
int getMinValueIndex(int a[], int len, int index)
{
    int minValue = a[index];
    int minValueInex = index;

    for (int i = index + 1; i < len; i++)
    {
        if (a[i] < minValue)
        {
            minValue = a[i];
            minValueInex = i;
        }
    }

    return minValueInex;
}

//从i ~ len中选择最小值，放到索引为i的位置(i = 0 ~ len（外层循环)）
void simpleSelectSort(int a[], int len)
{
    int minValueInex = 0;

    for (int i = 0; i< len; i++)
    {
        minValueInex = getMinValueIndex(a, len, i);
        if (minValueInex != i)
        {
            mySwap(a[i], a[minValueInex]);
        }
        myPrint(a, len, i);
    }
}

简单选择排序2

思路

通过依次比较和交换来完成选择最小值

####代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//内层循环从i+1 ~ len中依次与i进行比较，选择最小值，放到索引为i的位置(i = 0 ~ len（外层循环)）
void simpleSelectSort2(int a[], int len)
{
    for (int i = 0; i < len; i++)
    {
        for (int j = i + 1; j < len; j++)
        {
            if (a[j] < a[i])
            {
                mySwap(a[j], a[i]);
            }
        }
        myPrint(a, len, i);
    }
}

简单选择排序3(二元选择排序)

思路

通过每次遍历同时选择最小值和最大值，减少遍历次数为n/2

代码实现

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
//二元选择排序，每次从i ~ len-i中选择最大值和最小值，然后分别放入i和len-i-1的位置(i = 0 ~ len/2)
void simpleSelectSort3(int a[], int len)
{
    int minValueIndex = 0;
    int maxValueIndex = 0;

    for (int i = 0; i < len/2; i++) // i只需0~len/2
    {
        minValueIndex = i;
        maxValueIndex = i;

        for (int j = i+1; j < len-i; j++) //遍历i~len-i获取最大值和最小值索引
        {
            if (a[j] > a[maxValueIndex])
            {
                maxValueIndex = j;
                continue; // 满足大于当前最大值条件就没必要去下面比较最小值了
            }

            if (a[j] < a[minValueIndex])
            {
                minValueIndex = j;
            }
        }

        if (minValueIndex != i)
        {
            mySwap(a[i], a[minValueIndex]); // 获取的最小值与a[i]交换
        }
        if (maxValueIndex != len-i-1)
        {
            mySwap(a[len-i-1], a[maxValueIndex]); // 获取的最大值与a[len-i-1]交换
        }
        myPrint(a, len, i);
    }
}

简单选择排序结果打印

before sorted print:
loop[0]: 1 6 8 9 4 5 6 25 19 3 0 2
sorted process print:
loop[0]: 0 6 8 9 4 5 6 25 19 3 1 2
loop[1]: 0 1 8 9 4 5 6 25 19 3 6 2
loop[2]: 0 1 2 9 4 5 6 25 19 3 6 8
loop[3]: 0 1 2 3 4 5 6 25 19 9 6 8
loop[4]: 0 1 2 3 4 5 6 25 19 9 6 8
loop[5]: 0 1 2 3 4 5 6 25 19 9 6 8
loop[6]: 0 1 2 3 4 5 6 25 19 9 6 8
loop[7]: 0 1 2 3 4 5 6 6 19 9 25 8
loop[8]: 0 1 2 3 4 5 6 6 8 9 25 19
loop[9]: 0 1 2 3 4 5 6 6 8 9 25 19
loop[10]: 0 1 2 3 4 5 6 6 8 9 19 25
loop[11]: 0 1 2 3 4 5 6 6 8 9 19 25
after sorted print:
loop[0]: 0 1 2 3 4 5 6 6 8 9 19 25

堆排序

二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足二个特性：
1.父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值
2.每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）
当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆
当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆

思路

最小堆排序：(从大到小顺序)
1.建立最小堆
2.交换堆顶(最小值)和末尾位置
3.向下重新调整最小堆(不包括末尾位置)
4.循环2~3步骤(末尾位置不断变小)

代码实现

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
// 向下调整最小堆：当前位置index, 左右孩子节点分别为2*index+1和2*index+2
// 最小值上浮过程
void downAdjustMinHeap(int a[], int len, int index)
{
    int sonIndex = 2 * index + 1;
    int tmp = a[index]; // 交换第一步

    while (sonIndex < len)
    {
        if ((sonIndex+1 < len) && (a[sonIndex+1] < a[sonIndex])) // 获取左右孩子节点的较小值的索引
        {
            sonIndex++;
        }

        if (a[sonIndex] >= tmp)    // 若孩子结点不比当前值小，则退出
        {
            break;
        }

        // 若孩子结点比当前值小，则交换之
        a[index] = a[sonIndex]; // 交换第二步
        index = sonIndex;

        sonIndex = 2 * index + 1; //继续后续孩子结点比较
    }

    a[index] = tmp;  // 交换第三步,注意，此处索引为index,非sonIndex（因为sonIndex已经运算了一次sonIndex = 2*index + 1了）。
}


// 建立最小堆：从堆中最下面的非叶子节点(总共len/2-1个非叶子节点)开始依次往上使用(直到索引为0)向下调整最小堆的方法
void buildMinHeap(int a[], int len)
{
    for (int i = len/2-1; i >=0; i--)
    {
        downAdjustMinHeap(a, len, i);
    }
    std::cout << "build min heap result: ";
    myPrint(a, len);
}

// 最小堆排序
void minHeapSort(int a[], int len)
{
    buildMinHeap(a, len);
    for (int i = len-1; i >=1; i--)
    {
        mySwap(a[0], a[i]);
        downAdjustMinHeap(a, i, 0); // 每次都是从根节点0
        myPrint(a, len, i);
    }
}

堆排序结果打印

before sorted print:
loop[0]: 1 6 8 9 4 5 6 25 19 3 0 2
sorted process print:
build min heap result: loop[0]: 0 1 2 9 3 5 6 25 19 6 4 8
loop[11]: 1 3 2 9 4 5 6 25 19 6 8 0
loop[10]: 2 3 5 9 4 8 6 25 19 6 1 0
loop[9]: 3 4 5 9 6 8 6 25 19 2 1 0
loop[8]: 4 6 5 9 19 8 6 25 3 2 1 0
loop[7]: 5 6 6 9 19 8 25 4 3 2 1 0
loop[6]: 6 9 6 25 19 8 5 4 3 2 1 0
loop[5]: 6 9 8 25 19 6 5 4 3 2 1 0
loop[4]: 8 9 19 25 6 6 5 4 3 2 1 0
loop[3]: 9 25 19 8 6 6 5 4 3 2 1 0
loop[2]: 19 25 9 8 6 6 5 4 3 2 1 0
loop[1]: 25 19 9 8 6 6 5 4 3 2 1 0
after sorted print:
loop[0]: 25 19 9 8 6 6 5 4 3 2 1 0

直接插入排序

思路

将一个记录插入到一个已经排序好的序列中，从而得到一个新的，记录数+1的有序序列
即先将有序序列第一个元素当成有序序列，然后从第二个元素开始依次逐个进行插入，直到整个序列有序为止

  1. 初始时，a[0]自成1个有序区，无序区为a[1~n-1]。令i=1
  2. 将a[i]并入当前的有序区a[0i-1]中形成a[0i]的有序区间。
  3. i++并重复第二步直到i—>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
/*直接的插入排序
从哨兵开始从后向前比较
*/
void directInsertSort(int a[], int len)
{
    for (int i = 1; i < len; i++)
    {
        if (a[i] < a[i-1]) // 哨兵前一个元素比哨兵大则进行后移操作
        {
            int tmp = a[i]; // 暂存当前哨兵值
            int index = i - 1; // 暂存当前哨兵前一个元素的值
            a[i] = a[i-1]; // 后移一位当前哨兵值的前一个元素

            while (a[index] > tmp)  // 若当前哨兵值前面多个序列元素比哨兵值大，则哨兵值前面序列的较大元素依次循环后移
            {
                a[index + 1] = a[index];
                index--;
            }
            a[index + 1] = tmp; // 当前哨兵值插入合适为止，使当前哨兵值前一个元素刚好不大于其值
        }
        myPrint(a, len, i);
    }
}

直接插入排序结果打印

before sorted print:
loop[0]: 1 6 8 9 4 5 6 25 19 3 0 2
sorted process print:
loop[1]: 1 6 8 9 4 5 6 25 19 3 0 2
loop[2]: 1 6 8 9 4 5 6 25 19 3 0 2
loop[3]: 1 6 8 9 4 5 6 25 19 3 0 2
loop[4]: 1 4 6 8 9 5 6 25 19 3 0 2
loop[5]: 1 4 5 6 8 9 6 25 19 3 0 2
loop[6]: 1 4 5 6 6 8 9 25 19 3 0 2
loop[7]: 1 4 5 6 6 8 9 25 19 3 0 2
loop[8]: 1 4 5 6 6 8 9 19 25 3 0 2
loop[9]: 1 3 4 5 6 6 8 9 19 25 0 2
loop[10]: 0 1 3 4 5 6 6 8 9 19 25 2
loop[11]: 0 1 2 3 4 5 6 6 8 9 19 25
after sorted print:
loop[0]: 0 1 2 3 4 5 6 6 8 9 19 25

希尔排序

思路

先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的

代码实现

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
/*
通用的插入排序
直接插入排序中dk = 1;
*/
void shellInsertSort(int a[], int len, int dk)
{
    for (int i = dk; i < len; i++)
    {
        if (a[i] < a[i-dk]) // 哨兵前dk距离的元素比哨兵大则进行后移操作
        {
            int tmp = a[i];  // 暂存当前哨兵值
            int index = i - dk; // 暂存当前哨兵前dk距离的元素的值
            a[i] = a[i-dk]; // 后移dk位当前哨兵值的前dk距离的元素

            while (a[index] > tmp) // 若当前哨兵值前面多个距离为dk的序列元素比哨兵值大，则哨兵值前面序列的较大元素依次循环后移
            {
                a[index + dk] = a[index];
                index -= dk;
            }
            a[index + dk] = tmp; // 当前哨兵值插入合适为止，使当前哨兵值前dk距离的元素刚好不大于其值
        }
    }
}

/*
希尔排序： dk = len/2,len/4....,1;
减少增量的直接插入排序，直到增量为1
*/
void shellSort(int a[], int len)
{
    int dk = len / 2; //dk = len/2,len/4....,1;
    while (dk >=1)
    {
        shellInsertSort(a, len, dk);
        dk /= 2;
        myPrint(a, len, dk);
    }
}

希尔排序结果打印

before sorted print:
loop[0]: 1 6 8 9 4 5 6 25 19 3 0 2
sorted process print:
loop[3]: 1 6 8 3 0 2 6 25 19 9 4 5
loop[1]: 1 0 2 3 4 5 6 6 8 9 25 19
loop[0]: 0 1 2 3 4 5 6 6 8 9 19 25
after sorted print:
loop[0]: 0 1 2 3 4 5 6 6 8 9 19 25

归并排序

思路

基本思想是分治
先递归序列拆成多个有序序列，直到每个序列有一个元素，然后再合并有序序列

代码实现

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
//通用的合并两个有序序列a[len_a]和b[len_b]到最终有序序列res[]中
void commonMergeSortedSequence(int a[], int len_a, int b[], int len_b, int res[])
{
    int index = 0;
    int i = 0;
    int j = 0;

    while (i < len_a && j < len_b)
    {
        if (a[i] < b[j]) //结果中存入较小的a元素
        {
            res[index++] = a[i++];
        }
        else          //结果中存入较小的b元素
        {
            res[index++] = b[j++];
        }
    }

    while (i < len_a) // 结果中存入剩余的a元素
    {
        res[index++] = a[i++];
    }

    while (j < len_b) // 结果中存入剩余的b元素
    {
        res[index++] = b[j++];
    }   
}

/*归并排序*/
//合并有序序列a[left, mid]和 a[mid+1, right]到最终有序序列res[]中,初始化left = 0, right = len-1

void mergeArray(int a[], int left, int mid, int right, int res[])
{
    int i = left; // i 从[left,mid]包括mid
    int j = mid+1;  // j 从[mid+1,right]包括right
    int index = 0;

    while (i <= mid && j <= right)
    {
        if (a[i] < a[j])
        {
            res[index++] = a[i++];
        }
        else
        {
            res[index++] = a[j++];
        }
    }

    while (i <= mid)
    {
        res[index++] = a[i++];
    }
    while (j <= right)
    {
        res[index++] = a[j++];
    }

    // 将合并结果res[]赋给a[left,right),保持a[]有序，以便下面递归使用
    for (i = 0; i < index; i++)
    {
        a[left + i] = res[i];
    }
    myPrint(res, index);
}

// 归并排序
void mergeSort(int a[], int left, int right, int res[])
{
    if (left  < right)
    {
        int mid = (left + right)/2;
        mergeSort(a, left, mid, res); // 递归归并排序左边的有序序列
        mergeSort(a, mid+1, right, res); //递归 归并排序右边的有序序列
        mergeArray(a, left, mid, right, res); // 合并有序的左边和右边有序序列
    }
}

归并排序结果打印

before sorted print:
loop[0]: 1 6 8 9 4 5 6 25 19 3 0 2
sorted process print:
loop[0]: 1 6
loop[0]: 1 6 8
loop[0]: 4 9
loop[0]: 4 5 9
loop[0]: 1 4 5 6 8 9
loop[0]: 6 25
loop[0]: 6 19 25
loop[0]: 0 3
loop[0]: 0 2 3
loop[0]: 0 2 3 6 19 25
loop[0]: 0 1 2 3 4 5 6 6 8 9 19 25
after sorted print:
loop[0]: 0 1 2 3 4 5 6 6 8 9 19 25

线性排序

计数排序

思路

  1. 找出待排序的数组中最大和最小的元素
  2. 统计数组中每个值为i的元素出现的次数，存入数组CountArray的第i项
  3. 对所有的计数累加（从CountArray中的第一个元素开始，每一项和前一项相加）
  4. 反向填充目标数组：将每个元素i放在新数组的第CountArray(i)项，每放一个元素就将CountArray(i)减去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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
int getMaxValue(int a[], int len)
{
    int maxValue = a[0];
    for (int i = 0; i < len; i++)
    {
        if (a[i] > maxValue)
        {
            maxValue = a[i];
        }
    }
    return maxValue;
}

void countSort(int a[], int len, int res[])
{
    int maxValue = getMaxValue(a, len);
    int *countArray = new int[maxValue+1]; //  计数数组
    int i = 0;

    for (i = 0; i < maxValue+1; i++)
    {
        countArray[i] = 0;    // 初始化计数数组为0
    }

    for (i = 0; i < len; i++)
    {
        countArray[a[i]]++; // 计数a[]中每个元素的个数存入计数数组，且索引为元素值
    }

    for (i = 1; i < maxValue+1; i++)
    {
        countArray[i] += countArray[i - 1]; // 累加计数数组，最终计数数组中保存不小于元素值的计数个数，索引依然为元素值
    }

    for (i = 0; i < len; i++)
    {
        int element = a[i]; // 当前待排序元素a[i]值
        int sortIndex = countArray[element] - 1; // 当前元素a[i]在最终排序后有序序列中的位置索引
        res[sortIndex] = element; // 将当前元素a[i]放在最终排序后有序序列中的相应位置上
        countArray[element]--;  // 每次放入一个后，个数减一调整之
        myPrint(a, len, sortIndex);
    }

    delete []countArray;
}

计数排序运行结果打印

before sorted print:
loop[0]: 1 6 8 9 4 5 6 25 19 3 0 2
sorted process print:
loop[1]: 1 6 8 9 4 5 6 25 19 3 0 2
loop[7]: 1 6 8 9 4 5 6 25 19 3 0 2
loop[8]: 1 6 8 9 4 5 6 25 19 3 0 2
loop[9]: 1 6 8 9 4 5 6 25 19 3 0 2
loop[4]: 1 6 8 9 4 5 6 25 19 3 0 2
loop[5]: 1 6 8 9 4 5 6 25 19 3 0 2
loop[6]: 1 6 8 9 4 5 6 25 19 3 0 2
loop[11]: 1 6 8 9 4 5 6 25 19 3 0 2
loop[10]: 1 6 8 9 4 5 6 25 19 3 0 2
loop[3]: 1 6 8 9 4 5 6 25 19 3 0 2
loop[0]: 1 6 8 9 4 5 6 25 19 3 0 2
loop[2]: 1 6 8 9 4 5 6 25 19 3 0 2
after sorted print:
loop[0]: 0 1 2 3 4 5 6 6 8 9 19 25

桶排序

同计数排序一样，桶排序也对待排序序列作了假设，桶排序假设序列由一个随机过程产生，该过程将元素均匀而独立地分布在区间[0,1)上。基本思想是：把区间[0,1)划分成n个相同大小的子区间，称为桶。将n个记录分布到各个桶中去。如果有多于一个记录分到同一个桶中，需要进行桶内排序(可以使用快排)。最后依次把各个桶中的记录列出来记得到有序序列

基数排序

在计数排序中，当k很大时，时间和空间的开销都会增大（可以想一下对序列{12344,33333,6666}用计数排序，此时不但浪费很多空间，而且时间方面还不如比较排序）。于是可以把待排序记录分解成个位(第一位)、十位(第二位)….然后分别以第一位、第二位…对整个序列进行计数排序。这样的话分解出来的每一位不超过9，即用计数排序序列中最大值是9了