内部排序算法

发表于 分类于 ， Waline：
本文字数： 6.6k 阅读时长 ≈ 6 分钟
简单排序算法以及希尔排序、快速排序、堆排序、归并排序

各排序算法默认按照递增的顺序

简单排序

直接插入排序

主要思想

数组前部分有序,后部分无序,把无序部分的元素逐个插入到有序部分(元素后移)

代码

1
2
3
4
5
6
7
8
9
10
11
12
void InsertSort(int arr[], int n)
{
    for (int i = 1; i < n; i++) {  // 开始时有序部分只有0号元素，逐个遍历后面的无序元素
        if (arr[i] < arr[i - 1]) { // 如果需要向前插入
            int tmp = arr[i], j;
            for (j = i - 1; j >= 0 && arr[j] > tmp; j--) { // 边寻找插入位置边把元素后移
                arr[j + 1] = arr[j];
            }
            arr[j + 1] = tmp;      // 现在j指向的元素不大于tmp，j+1就是最终的插入位置
        }
    }
}

简单选择排序

主要思想

数组前部分有序,后部分无序,每次从无序部分选择最小值放到有序部分的后面

这个放的操作可以有两种方法:

  1. 将元素逐个后移从而空出位置.移动元素与直接插入排序的移动元素不同的是,这里移动的是无序部分,而直接插入排序移动的是有序部分
  2. 直接与无序部分的第一个元素交换,这比移动元素要高效,但是因为跳跃性地移动元素,会导致算法不稳定

关于排序算法稳定性: 算法不稳定是指本来序列中关键字相同的元素,在排序之后顺序发生了改变

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void SelectSort(int arr[], int n)
{
    for (int i = 0; i < n; i++) {         // 开始时0~n-1都是无序的
        int minIdx = i;
        for (int j = i + 1; j < n; j++) { // 查找无需部分的最小值的下标
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        if (minIdx != i) {			     // 最小值与无序部分的第一个元素交换
            int tmp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = tmp;
        }
    }
}

起泡排序

主要思想

前部分无序,后部分有序.将数组扫描n趟,一边扫描一边将不符合顺序的相邻两个元素交换,每趟扫描下来都会将无序部分的最大值交换到无序部分的最后面

如果一趟扫描中没有发生交换,则表明所有关键字都已经有序,可以提前结束.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void BubbleSort(int arr[], int n)
{
    for (int i = 0; i < n; i++) { // n趟扫描
        bool flag = false;        // 这一趟扫描是否发生了交换
        for (int j = 0; j < n - i - 1; j++) { // 只需要扫描无序部分，而每趟扫描会产生一个最大值，使无序部分的长度减一，因此只需要扫描n-i-1个
            if (arr[j] > arr[j + 1]) { // 相邻元素不符合顺序则交换
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
                flag = true;
            }
        }
        if (!flag) {              // 一趟扫描没有发生交换，提前结束
            break;
        }
    }
}

希尔排序

主要思想

希尔排序也叫缩小增量排序,是对直接插入排序的改进，主要是针对直接插入排序的两个缺点进行改进。

  1. 当n值很大时,由于要移动元素,复杂度很高
  2. 元素无序时复杂度最高

希尔排序就是通过一定的增量,将原序列划分为小序列，先对小序列进行直接插入排序，然后逐步减小增量，继续直接插入排序.到最后增量为1时，序列已经基本有序，再进行直接插入排序，复杂度会低很多。

代码

就是在直接插入排序外面套了一层增量循环，并将原来所有的1都换成了增量gap(j--也要换成j-=gap)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void ShellSort(int arr[], int n)
{
    for (int gap = (n >> 1); gap > 0; gap >>= 1) {  // 初始增量为n/2,之后逐渐减半
        for (int i = gap; i < n; i++) {
            if (arr[i] < arr[i - gap]) {
                int tmp = arr[i], j;
                for (j = i - gap; j >= 0 && arr[j] > tmp; j -= gap) {
                    arr[j + gap] = arr[j];
                }
                arr[j + gap] = tmp;
            }
        }
    }
}

快速排序

主要思想

快速排序可以看成是对起泡排序的改进。

起泡排序每趟遍历都会使无序部分的最值被移动到正确位置，也就是最后面，从而加入有序部分，于是无序部分长度减一，所以起泡排序中无序部分的减少是线性的。而快速排序是将一个中等大小的元素放到正确位置，然后用分治的思想，分别对这个中等大小的元素的前面和后面部分进行排序。而这个中等大小的元素被称为枢轴(pivot)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void QuickSort(int arr[], int low, int high)
{
    if (low < high) {
        int pivot = arr[low];
        int i = low, j = high;
        while (i < j) {
            while (i < j && arr[j] >= pivot) j--;
            if (i < j) {
                arr[i++] = arr[j];
            }
            while (i < j && arr[i] < pivot) i++;
            if (i < j) {
                arr[j--] = arr[i];
            }
        }
        arr[i] = pivot;
        QuickSort(arr, low, i - 1);
        QuickSort(arr, i + 1, high);
    }
}

优化

在序列基本有序时（比如这个正好按照递减的顺序），如果快速排序中的枢轴还是取当前序列的第一个，则最后这个枢轴会和起泡排序一样被放到序列的一端，也就是说这时的快速排序蜕化为了起泡排序！

为了解决这个问题，只需要选择中等大小的枢轴就行了，比较简单的做法是在序列第一个元素、中间元素和最后一个元素之中选择中等大小的。为了使代码不变，可以将这个中等大小的元素与序列第一个元素进行交换。

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
void inline Swap(int& a, int& b)
{
    int t = a;
    a = b;
    b = t;
}

void QuickSort(int arr[], int low, int high)
{
    if (low < high) {
        int mid = low + ((high - low) >> 1);  // low+high可能会溢出
        if (mid != low) {
            if (arr[low] > arr[mid] && arr[low] > arr[high]) {      // arr[low]在三者中最大
                Swap(arr[low], arr[mid] > arr[high] ? arr[mid] : arr[high]);
            }
            else if (arr[low] < arr[mid] && arr[low] < arr[high]) { // arr[low]在三者中最小
                Swap(arr[low], arr[mid] < arr[high] ? arr[mid] : arr[high]);
            }
        }
        int pivot = arr[low];
        int i = low, j = high;
        while (i < j) {
            while (i < j && arr[j] >= pivot) j--;
            if (i < j) {
                arr[i++] = arr[j];
            }
            while (i < j && arr[i] < pivot) i++;
            if (i < j) {
                arr[j--] = arr[i];
            }
        }
        arr[i] = pivot;
        QuickSort(arr, low, i - 1);
        QuickSort(arr, i + 1, high);
    }
}

堆排序

主要思想

在前面的简单选择排序中，每次都要通过遍历无序部分来查找最值，效率比较低，而堆排序就是针对这个找最值的过程进行优化，用到的数据结构是堆。这里的堆实际是一个用数组存储的完全二叉树。

完全二叉树的性质：

  1. 数组下标从0开始时，完全二叉树的一个结点i的左孩子的下标是2i+1（如果有左孩子），右孩子的下标是2i+2（如果有右孩子）。
  2. 完全二叉树的最后一个非叶子结点的下标为n/2-1（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
void HeapSort(vector<int>& arr){ // 堆排序
    for(int i = arr.size() / 2 - 1; i >= 0; i--){ // 从最后一个非叶子开始
        adjustHeap(arr, i, arr.size() - 1);       // 逐个调整以其为根的子树形成大顶堆
    }
    for(int i = arr.size() - 1; i > 0; i--){      // 从最后一个叶子开始（选择排序，前部分无序，后部分有序）
        swap(arr[0], arr[i]);                     // 逐个与树根进行交换（选出最大值放到无序部分的最后面，有序部分向前扩增）
        adjustHeap(arr, 0, i - 1);                // 调整剩余元素0~i-1，使之仍然满足大顶堆的性质
    }
} 

void adjustHeap(vector<int>& arr, int low, int high){ // 当前树中的元素为low~high，对根节点low进行下沉调整（将其下放到正确的位置以保持大顶堆的性质）
    int tmp = arr[low]; // 暂存根节点的值
    int i = low;        // 根节点最终位置
    // 下面k表示子结点中较大者（先指向左子节点，然后与右子节点进行比较）
    for(int k = i * 2 + 1; k <= high; k = k * 2 + 1){ // 先指向其左子节点（下标从0开始的完全二叉树的性质：i的左子节点是2*i+1）
        if(k + 1 <= high && arr[k] < arr[k+1]){       // 如果右子节点的值更大
            k++;                                      // 则将k指向右子节点
        }
        if(arr[k] > tmp){    // 如果较大的子节点的值比父节点的值大（需要把大的节点提上来，父节点沉下去）
            arr[i] = arr[k]; // 则将此父节点与之进行交换，为了优化，实际上并没有交换
            i = k;           // 而是仅仅将子节点的值赋给父节点，然后把位置索引i改为指向子节点即可（父节点的值一直保存在tmp里）
        } // 如果子节点还有子节点，则继续进行递归式的调整（不过这里是按照循环进行，之后依然是先指向左子节点(*2+1)，然后看右子节点）
        else{ 				
            break;           // 父节点大于左右子节点，说明已经找到正确的位置了
        }
    }
    arr[i] = tmp; // 最终确定节点值的位置（要么同时大于左右子节点，要么就是到达了叶子），类似于快速排序里最后确定枢轴的位置
}

另一种比较简洁的调整函数为下沉(Sink)，通过递归进行处理，效率稍微差一些。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void Sink(int arr[], int low, int high)
{
    int leftChild = (low >> 1) + 1;
    int rightChild = leftChild + 1;
    int present = low;
    if (leftChild <= high && arr[leftChild] > arr[present]) {  // 有左孩子且左孩子大
        present = leftChild;
    }
    if (rightChild <= high && arr[rightChild] > arr[present]) {// 有右孩子且右孩子大
        present = rightChild;
    }
    if (present != low) {
        Swap(arr[low], arr[present]);// 父与较大的孩子换
        Sink(arr, present, high);    // 递归处理子树
    }
}

归并排序

主要思想

归并排序就是纯粹的分治思想，先递归地将前半部分序列和后半部分序列排好，然后合并这两个序列就能完成整个序列的排序。

如果是自底向上（也就是递归到最后不可再分时）来看，归并排序是将初始的n个元素看成是n个有序的子序列，然后两两归并为有序序列，最后归并为一整个长为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
void Merge(int arr[], int tmp[], int low, int mid, int high)
{
    for (int i = low; i <= high; i++) {
        tmp[i] = arr[i];
    }
    int i = low, left = low, right = mid + 1;
    while (left <= mid && right <= high) {
        arr[i++] = tmp[left] < tmp[right] ? tmp[left++] : tmp[right++];
    }
    while (left <= mid) {
        arr[i++] = tmp[left++];
    }
    while (right <= high) {
        arr[i++] = tmp[right++];
    }
}

void MergeSort(int arr[], int tmp[], int low, int high)
{
    if (low < high) {
        int mid = low + ((high - low) >> 1); 
        MergeSort(arr, tmp, low, mid);      // 排左半部分（注意细节：左半部分上界不是mid-1，不然无穷递归！）
        MergeSort(arr, tmp, mid + 1, high); // 排右半部分
        Merge(arr, tmp, low, mid, high);    // 合并
    }
}

void MergeSort(int arr[], int n)
{
    int* const tmp = new int[n];
    MergeSort(arr, tmp, 0, n - 1);
    delete[] tmp;
}

优化

如果用自底向上的方法，可以将归并排序改成迭代版本的

1
2
3
4
5
6
7
8
9
10
11
12
void MergeSort(int arr[], int n)
{
    int* tmp = new int[n];
    for (int gap = 1; gap < n; gap <<= 1) {
        for (int low = 0; low < n; low += (gap << 1)) {
            int high = low + (gap << 1) - 1;
            int mid = (low + high) >> 1;
            Merge(arr, tmp, low, mid >= n ? n - 1 : mid, high >= n ? n - 1 : high);
        }
    }
    delete[] tmp;
}
相关文章