基本概念

• 排序的稳定性
  任意两个相等的数据，排序前后相对位置不发生改变

题目

给定N个（长整型范围内的）整数，要求输出从小到大排序后的结果。

本题旨在测试各种不同的排序算法在各种数据情况下的表现。各组测试数据特点如下：

• 数据1：只有1个元素；
• 数据2：11个不相同的整数，测试基本正确性；
• 数据3：1000个随机整数；
• 数据4：10000个随机整数；
• 数据5：100000个随机整数；
• 数据6：100000个顺序整数；
• 数据7：100000个逆序整数；
• 数据8：100000个基本有序的整数；
• 数据9：100000个随机正整数，每个数字不超过1000。

代码合集

//
// Created by allenhsu on 2018/11/28.
//

#include <iostream>
using namespace std;
int N;
int list[100000];

void Swap(int a, int b){
    int temp = list[a];
    list[a] = list[b];
    list[b] = temp;
}

// 冒泡排序： 两个相邻的元素做比较
void Bubble_sort(){
    for (int i = N - 1; i > 0; --i) {
        int flag = 0;
        for (int j = 0; j < i; ++j) {
            if (list[j] > list[j + 1]) {
                Swap(j,j+1);
                flag = 1;
            }
        }
        if (!flag) break;
    }
}

// 一直保证前面的序列是递增的
void Insert_Sort(){
    for (int i = 1; i < N; ++i) {
        for (int j = i - 1; j >= 0 && list[j] > list[j + 1]; --j) {
            Swap(j, j + 1);
        }
    }
}

int main(){
    cin >> N;
    for (int i = 0; i < N; ++i) {
        cin >> list[i];
    }

    Insert_Sort();
    cout << list[0];
    for (int j = 1; j < N; ++j) {
        cout <<  " " << list[j];
    }
    return 0;
}

测试结果

• 冒泡排序

  
  image.png

• 插入排序

  
  插入排序算法

• 希尔排序—插入排序的改进
  三层循环，第一层，决定步长的大小；第二层，决定比较的两个数之一；第三层，决定第二个比较数字。所以要跨步长的作比较，我们的步长需要在第三层中加入即可。
  下图可以看出已经很快了。
  希尔排序是不稳定的，因为最开始大步长的时候，是跳着来的。

  
  希尔排序

• 选择排序
  每一次从剩余所有中选最小的，放在已经排好序的末尾

  
  选择排序

• 堆排序—选择排序的改进
  选择排序中最费时间的是每次找出剩余元素中的最小元。这正是最小堆的用武之地。
  两种方法：

  1. 先从list建立起来MinHeap, 然后新建一个临时templist, 将MinHeap弹出依次放入templist中，最后在将templist复制回list；

  2. 聪明的不费空间的方法：从list建立起一个最大堆MaxHeap, 每次将最大元素与末尾元素交换，然后MaxHeap扔掉最后的元素重新生成最大堆

     
     堆排序

• 归并排序

• 快排

• 表排序

• 基数排序