八大排序

八大排序 - Shuai-Xie - Github

内部排序和外部排序

  • 内部排序数据少，数据记录在内存中进行排序，八大排序都是内部排序。
  • 外部排序数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。

当 n 较大，则应采用时间复杂度为 O(nlog2n) 的排序方法：快速排序、堆排序或归并排序。快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短。

各种排序的稳定性，时间复杂度和空间复杂度总结：

八大排序复杂度

1. 直接插入排序

  • 基本思想：将一个记录插入到已排序好的有序表中，从而得到一个新的记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。
  • 要点：设立哨兵，作为 临时存储 和 判断数组边界 之用。
    有哨兵是将要排序的元素保存为 a[0]，而不是再：int x
  • 稳定：如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变（因为从后往前插，相同的元素，后插入的仍然排在后面），所以插入排序是稳定的。
  • 时间复杂度： O（n2）
直接插入排序示例
  • 有哨兵
void insertSort( int *a, int len) {

    // 数组后移
    auto *b = new int[len + 1];
    for (int i = 1; i <= len; ++i) {
        b[i] = a[i - 1];
    }

    // 有哨兵插入排序
    for (int i = 2; i <= len; ++i) { // len是b数组中最后一个元素的下标
        if (b[i] < b[i - 1]) { // 要插入的元素 < 已有序数列的最大元素
            b[0] = b[i];
            int j = i - 1; // 已有序序列的最后一个元素
            while (b[0] < b[j]) { // 此处与无哨兵相比少了一个判断条件
                b[j + 1] = b[j];
                j--;
            } // 跳出时，b[j]<=b[0]
            b[j + 1] = b[0];
        }
    }

    // 排序好后传给a
    for (int i = 1; i <= len; ++i) {
        a[i - 1] = b[i];
    }
}
  • 无哨兵
void insertSort(int *arr, int len) {
    for (int i = 1; i < len; ++i) { // 从第2个元素开始插入，原始单个元素视为有序
        if (arr[i] < arr[i - 1]) { // 如果相邻的2个数不是有序 再排序
            int x = arr[i]; // x 是要插入的元素
            int j = i - 1; // 已有序序列的最后一个
            while (arr[j] > x && j >= 0) { // j >=0 防止数组越界
                arr[j + 1] = arr[j]; // 循环内满足：arr[j] > x 元素后移1位
                j--;
            }  // 跳出循环时，arr[j] <= x，x 插入在 j+1
            arr[j + 1] = x; 
        }
    }
}
带哨兵的插入排序中的哨兵元素 a[0] 有两个作用：
  1. 临时存放待插入元素
  2. 防止数组下标越界
    当待插入的元素 < 已排序的子数组中的最小元素时，j=-1，越界
    而采用哨兵，arr[0] < arr[j]，当 j=0 时，就结束循环，不会出现越界
    （while 循环只有一次判断，提高了效率）
  • 但是存在一个问题：原始数组如果从 a[0] 开始，则插入第一个元素时，a[0]会被覆盖，造成最终排完序的数组缺少了原始数组的第一个元素。
  • 消除此问题：在调用此方法之前，将数组做下处理，使其右移一个元素的位置，空出来的第0个元素初始化为0（或不做初始化）
  • 无哨兵的插入排序，无上述问题，但在效率上会稍低，while 循环中有两个判断条件。
  • 摘录 - 直接插入排序（哨兵和越界）

2. Shell排序

希尔排序又叫缩小增量排序，在直排基础上改进。
增量序列通常为：d = {n/2 ,n/4, n/8 .....1} 依次减小，最后必须为1。

  • 基本思想：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
  • 不稳定：因为有元素交换。
  • 复杂度：取决于增量因子序列d的选取，目前还没有选取最好的增量因子序列的方法。
  • 操作方法：如下图示例。

希尔排序的示例：

非递归实现

void shellSort(int *arr, int len) {
    for (int dk = len / 2; dk > 0; --dk) { // dk增量
        for (int i = dk; i < len; ++i) { // 1层for
            if (arr[i] < arr[i - dk]) {
                int x = arr[i]; // 哨兵
                int j = i - dk; // 原有序序列最后一个元素
                while (x < arr[j] && j >= 0) {
                    arr[j + dk] = arr[j];
                    j -= dk;
                }
                arr[j + dk] = x;
            }
        }
    }
}

递归实现

// dk是shell排序的增量
void shellInsertSort(int *arr, int len, int dk) {
    // 一层for 
    for (int i = dk; i < len; ++i) { // i=dk，其实是以dk为增量的子序列的第2个元素，与基本插入排序一样从第2个元素开始

        if (arr[i] < arr[i - dk]) {
            int x = arr[i]; // 哨兵
            int j = i - dk;

            while (x < arr[j] && j >= 0) { // 一定要判断j>0，因为while循环体中j会<0
                arr[j + dk] = arr[j];
                j -= dk;
            }
            // 跳出时，x >= arr[j]
            arr[j + dk] = x;
        }
    }
}

void shellSort(int *arr, int len) {
    int dk = len / 2;
    while (dk >= 1) {
        shellInsertSort(arr, len, dk);
        dk /= 2;
    }
}

注意：最外层for是dk..len-1，相当于从arr[dk]开始，把后面的元素都进行了插入排序，比如上图一趟排序的结果，增量为3，先插入55，再插入4，而不是先完成 13, 55, 38, 76 这4个数的排序。如果想一次完成，需要写2个for，其实参加排序的数是一样的。

void shellInsertSort(int *arr, int len, int dk) {
    // 两层for
    for (int k = 0; k < dk; ++k) { // 每次完成从arr[k]开始的增量序列
        for (int i = k + dk; i < len; i += dk) { // 第2个元素开始 
            // 内部不变
            if (arr[i] < arr[i - dk]) {
                int x = arr[i]; // 哨兵
                int j = i - dk;
                while (x < arr[j] && j >= 0) { // 一定要判断j>0，因为while循环体中j会<0
                    arr[j + dk] = arr[j];
                    j -= dk;
                }
                // 跳出时，x >= arr[j]
                arr[j + dk] = x;
            }
        }
    }
}

3. 直接选择排序

最小值放前思想

// 选择排序
void selectSort(int *arr, int len) {
    for (int i = 0; i < len - 1; ++i) {
        for (int j = i + 1; j < len; ++j) {
            if (arr[i] > arr[j]) swap(arr[i], arr[j]); // 最小值放前思想
        }
    }
}

4. 堆排序

堆排序是一种树形选择排序，是对直接选择排序的有效改进。

  • 基本思想：将序列调整成大顶堆，然后 swap(arr[0], arr[len-1])，最大值放后的思想，然后再将剩下的序列调整成大顶堆，再将次大值放后……
  • 误区：依次从 0..len-2 到 len-1 建立小顶堆，这是一种思路，但是这样去掉的是堆顶，直接就破坏了堆结构，而大顶堆去掉的是堆尾，不会破坏堆结构。
大顶 小顶
构建小顶堆
输出堆顶后调整堆
// 调整大顶堆
void heapAdjust(int *arr, int root, int len) {
    int child = 2 * root + 1;
    while (child < len) { // child可以去最后一个元素：len-1
        if (child + 1 < len && arr[child] < arr[child + 1]) child++; // child指向大孩子
        if (arr[root] < arr[child]) {
            swap(arr[root], arr[child]);
            root = child;
            child = 2 * root + 1;
        } else {
            break; // 基于下面已经满足大顶堆
        }
    }
}

// 构建大顶堆
void buildHeap(int *arr, int len) {
    for (int i = (len - 1) / 2; i >= 0; --i) { // (length-1)/2 最大的非叶节点
        heapAdjust(arr, i, len); // i遍历所有的root
    }
}

// 4.堆排序
void heapSort(int *arr, int len) {
    buildHeap(arr, len);
    cout << "调整之后";
    printArr(arr, len);
    while (len > 1) { 
        swap(arr[0], arr[len - 1]); // 首尾元素互换
        cout << "len=" << len;
        printArr(arr, len);
        len--;
        heapAdjust(arr, 0, len);
    }
}

          49   38   65   97   76   13   27   49   55    4
build     97   76   65   55   49   13   27   49   38    4
len=10     4   76   65   55   49   13   27   49   38   97
len=9     38   55   65   49   49   13   27    4   76
len=8      4   55   38   49   49   13   27   65
len=7     27   49   38    4   49   13   55
len=6     13   49   38    4   27   49
len=5     13   27   38    4   49
len=4      4   27   13   38
len=3     13    4   27
len=2      4   13
    4   13   27   38   49   49   55   65   76   97

5. 冒泡排序

最大值放后思想

// 冒泡排序
void bubbleSort(int *arr, int len) {
    for (int i = 0; i < len - 1; ++i) {
        for (int j = 0; j < len - 1 - i; ++j) {
            if (arr[j] > arr[j + 1]) swap(arr[j], arr[j + 1]); // 最大值放后思想
        }
    }
}

6. 快速排序

基本思想：

  1. 选择一个基准元素,通常选择第一个元素或者最后一个元素,
  2. 通过一趟排序将序列分成两部分，一部分比基准值小，另一部分比基准值大。
  3. 此时基准元素正好在其排好序后的正确位置（第k小数）
  4. 然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。

寻找 pivot 的位置很关键。

// 分成两部分
int partition(int *arr, int low, int high) {
    int pivot = arr[low]; // 选第1个值为基准值
    while (low < high) {
        while (low < high && arr[high] >= pivot) high--;
        swap(arr[high], arr[low]); // 大小值更换，注意：更换的不是pivot
        while (low < high && arr[low] <= pivot) low++;
        swap(arr[high], arr[low]); // 大小值更换
    }
    return low;
}

void quickSort(int *arr, int low, int high) {
    if (low < high) {
        int pivotLoc = partition(arr, low, high); // 基准值位置
//        printArr(arr, high + 1);
        quickSort(arr, low, pivotLoc - 1);
        quickSort(arr, pivotLoc + 1, high);
    }
}

7. 归并排序

  • 基本思想：归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

归并排序示例：

void merge(int *arr, int low, int mid, int high) {
    int tmp[high - low + 1]; // 暂存数据

    // 3个序列迭代器
    int i = low; // 序列1开始
    int j = mid + 1; // 序列2开始
    int k = 0; // 合并新序列开始

    while (i <= mid && j <= high) { // 都得小于最后一个元素
        tmp[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
    }

    while (i <= mid) tmp[k++] = arr[i++];
    while (j <= high) tmp[k++] = arr[j++];

    i = low; // arr序列开始的位置
    k = 0;
    while (i <= high) arr[i++] = tmp[k++];
}

void mergeSort(int *arr, int low, int high) {
    int mid;
    if (low < high) {
        mid = (low + high) / 2;
        mergeSort(arr, low, mid); // 这里和merge中的j值有关
        mergeSort(arr, mid + 1, high); // 先mergeSort成2个有序序列，再将2个序列合并有完整有序
        merge(arr, low, mid, high);
    }
}

8. 基数排序

  • 基本思想：把数据分组，放在一个个的桶中，然后对每个桶里面的在进行排序。

  • 操作方法：例如要对大小为 [1..1000] 范围内的 n 个整数 A[1..n] 排序：

    1. 把桶设为大小为10的范围，具体而言，设集合 B[1] 存储 [1..10] 的整数，集合B[2] 存储 [11..20] 的整数……总共100个桶
    2. 对 A[1..n] 从头到尾扫描一遍，把每个 A[i] 放入对应的桶 B[j] 中
    3. 再对这100个桶中每个桶里的数字排序，可用任何排序方法
    4. 依次输出每个桶里面的数字。

  • 复杂度：
    假设有n个数字，m个桶，如果数字是平均分布的，每个桶里面平均有n/m个数字
    如果对每个桶中的数字采用快速排序，那么整个算法的复杂度是：
    O(n + m × n/m×log(n/m)) = O(n + n(log(n/m)))
    从上式看出，当 m 接近 n 的时候，桶排序复杂度接近O(n)
    当然，以上复杂度的计算是基于输入的n个数字是平均分布这个假设的。这个假设是很强的 ，实际应用中效果并没有这么好。如果所有的数字都落在同一个桶中，那就退化成一般的排序了。

  • 特点：非常耗费空间，如果能实现每个桶刚好1个数字，这是数列就已经有序了。

void radixSort(int *arr, int len, int radix) {

    // 先找到待排序元素的上下界
    int max = arr[0];
    int min = arr[0];
    for (int i = 1; i < len; ++i) {
        if (max < arr[i]) max = arr[i];
        if (min > arr[i]) min = arr[i];
    }
//    cout << max << "\t" << min << endl;

    int bucket_num = max / radix - min / radix + 1; // 桶的数量，一定要分开除
    int bucket_arr[bucket_num][len]; // 存储元素
    int bucket_len[bucket_num]; // 记录每个桶的元素个数

    for (int i = 0; i < bucket_num; ++i) bucket_len[i] = 0; // 赋初值

    // 元素进入桶
    cout << "元素进桶" << endl;
    for (int i = 0; i < len; ++i) {
        int bucket_id = arr[i] / radix - min / radix; // 桶id转移到数列下标，一定要分开除
        bucket_arr[bucket_id][bucket_len[bucket_id]] = arr[i];
        bucket_len[bucket_id]++;
    }

    // 打印各桶元素
    for (int i = 0; i < bucket_num; ++i) {
        cout << radix * (min / radix + i) << "," << radix * (min / radix + i + 1) - 1 << ": ";
        printArr(bucket_arr[i], bucket_len[i]);
    }

    cout << "桶内排序" << endl;
    for (int i = 0; i < bucket_num; ++i) {
        if (bucket_len[i] > 1) quickSort(bucket_arr[i], 0, bucket_len[i] - 1);
    }

    // 打印排序后各桶元素
    for (int i = 0; i < bucket_num; ++i) {
        cout << radix * (min / radix + i) << "," << radix * (min / radix + i + 1) - 1 << ": ";
        printArr(bucket_arr[i], bucket_len[i]);
    }

    // 排序后元素拷贝
    int k = 0;
    for (int i = 0; i < bucket_num; ++i) {
        for (int j = 0; j < bucket_len[i]; ++j) {
            arr[k] = bucket_arr[i][j];
            k++;
        }
    }
}

 83   86   77   15   93   35   86   92   49   21   62   27   90   59   63   26   40   26   72   36

元素进桶
10,19:    15
20,29:    21   27   26   26
30,39:    35   36
40,49:    49   40
50,59:    59
60,69:    62   63
70,79:    77   72
80,89:    83   86   86
90,99:    93   92   90

桶内排序
10,19:    15
20,29:    21   26   26   27
30,39:    35   36
40,49:    40   49
50,59:    59
60,69:    62   63
70,79:    72   77
80,89:    83   86   86
90,99:    90   92   93

   15   21   26   26   27   35   36   40   49   59   62   63   72   77   83   86   86   90   92   93

文章参考

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 194,491评论 5赞 459
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 81,856评论 2赞 371
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 141,745评论 0赞 319
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 52,196评论 1赞 263
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 61,073评论 4赞 355
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 46,112评论 1赞 272
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 36,531评论 3赞 381
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 35,215评论 0赞 253
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 39,485评论 1赞 290
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 34,578评论 2赞 309
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 36,356评论 1赞 326
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 32,215评论 3赞 312
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 37,583评论 3赞 299
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 28,898评论 0赞 17
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,174评论 1赞 250
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 41,497评论 2赞 341
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 40,697评论 2赞 335