排序算法总复习

基础概念

稳定: 如果a原本在b前面, 而a=b, 排序之后a仍然在b的前面不稳定: 如果a原本在b的前面, 而a=b, 排序之后a可能会出现在b的后面内排序: 所有排序操作都在内存中完成外排序: 由于数据太大, 因此把数据放在磁盘中, 而排序通过磁盘和内存的数据传输才能进行时间复杂度: 一个算法执行所耗费的时间空间复杂度: 运行完一个程序所需内存的大小


排序算法

1. 冒泡排序 bubble sort

1.1 算法描述:

  • 比较相邻的元素. 如果第一个比第二个大, 就交换它们两个

  • 对每一对相邻元素作同样的工作, 从开始第一对到结尾的最后一对, 这样在最后的元素应该会是最大的数

  • 针对所有的元素重复以上的步骤, 除了最后一个

  • 重复步骤1~3, 直到排序完成

1.2 核心代码:

void bubble_sort(int a[], int n) {
    int last_swap;
    int tmp = 0;
    for (int j = n - 1; j > 0; j = last_swap) {
        last_swap = 0;          // 每轮初始化为0, 防止死循环
        // 每轮循环比较相邻两元素的大小, 满足条件就交换位置
        for (int i = 0; i < j; i++) {
            if (a[i] > a[i + 1]) {
                tmp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = tmp;
                last_swap = i;  // 最后一次交换的位置
            }
        }
    }
}

1.3 算法分析

时间复杂度:

  • 最佳 T(n) = O(n)

  • 最差 T(n) = O(n^2)

  • 平均 T(n) = O(n^2)


2. 选择排序 selection sort

2.1 算法描述

  • 首先在未排序序列中找到最小/大元素, 存放到排序序列的起始位置

  • 然后,再从剩余未排序元素中继续寻找最小/大元素,然后放到已排序序列的末尾

  • 以此类推, 直到所有元素均排序完毕

2.2 核心代码:

void selection_sort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        // 找出最小元素的下标
        for (int pos = i, int j = i + 1; j < n; j++) {
            if (a[pos] > a[j]) {
                pos = j;
            }
        }

        // 将最小的元素放到本次循环的起始位置
        if (pos != i) {
            tmp = a[i];
            a[i] = a[pos];
            a[pos] = tmp;
        }
    }
}

2.3 算法分析

时间复杂度:

  • 最佳 T(n) = O(n^2)

  • 最差 T(n) = O(n^2)

  • 平均 T(n) = O(n^2)


3. 插入排序 insertion sort

3.1 算法描述

  • 从第一个元素开始, 将该元素认为是已被排序

  • 取出下一个元素, 在已经排序的元素序列中从后向前扫描

  • 如果该元素(已排序元素)大于新元素, 将该元素移到下一个位置

  • 重复步骤3, 直到找到已排序的元素小于或等于新元素的位置

  • 将新元素插入到该位置之后

  • 重复步骤2-5

3.2 核心代码:

void insertion_sort(int a[], int n) {
    int value;
    // i 代表的是当前要排序的元素下标, j 代表前面已排序的数组元素个数
    for (int i = 1; i < n; i++) {
        value = a[i];
        // 如果第i个元素小于第j个, 则第j个元素向后移动
        for (int j = i - 1; j >= 0 && value < a[j]; j--) {
            a[j + 1] = a[j];
        }

        a[j + 1] = value;
    }
}

3.3 算法分析

时间复杂度:

  • 最佳 T(n) = O(n^2)

  • 最差 T(n) = O(n^2)

  • 平均 T(n) = O(n^2)


4. 归并排序 merge sort

4.1 算法描述

  • 采用分治法, 先使每个字序列有序

  • 把长度为N 的输入序列分成两个长度为N/2 的子序列

  • 对这两个子序列再分别采用归并排序

  • 将两个排序好的子序列合并为一个最终排序序列

4.2 核心代码:

void merge_array(int a[], int first, int mid, int last, int temp[]) {
    int i = first;
    int j = mid + 1;
    int m = mid;
    int n = last;
    int k = 0;

    // 分别从左右数组中按大小顺序取出数据放入temp[]
    while (i <= m && j <= n) {
        if (a[i] <= a[j]) {
            temp[k++] = a[i++];
        } else {
            temp[k++] = a[j++];
        }
    }

    // 将左边数组中剩余数据按顺序放入temp[]
    while (i <= m) {
        temp[k++] = a[i++];
    }

    // 将右边数组中剩余数据按顺序放入temp[]
    while (j <= n) {
        temp[k++] = a[j++];
    }

    // 将temp[] 中数据放入a[]
    for (i = 0; i < k; i++) {
        a[first + i] = temp[k];
    }
}

void merge_sort(int a[], int first, int last, int temp[]) {
    if (first < last) {
        int mid = (first + last) / 2;
        merge_sort(a, first, mid, temp);        // 左边数组有序
        merge_sort(a, mid + 1, last, temp);     // 右边数组有序
        merge_array(a, fisrt, mid, last, temp); // 左右有序数组合并
    }
}

4.3 算法分析

时间复杂度:

  • 最佳 T(n) = O(n)

  • 最差 T(n) = O(nlogn)

  • 平均 T(n) = O(nlogn)


5. 快速排序 quick sort

5.1 算法描述

  • 从数组中选择第一个元素作为基准base(下标为0)

  • 数组的最右边元素下标为j, 最左边选定下标i=1的元素

  • 从最右边开始搜索, 即每一步j–, 直到找到一个元素的值小于base, 停止搜索

  • 然后从最左边开始搜索, 即每步i++, 直到找找到一个元素值大于base, 停止搜索

  • 交换此时的两个元素的值

  • 继续从右边开始搜索, 直到找到一个元素的值小于base, 停止搜索

  • 然后继续从左边开始搜索, 即每步i++, 直到找找到一个元素值大于base, 停止搜索

  • 交换此时的两个元素的值

  • 当 j == i 时, 将基准数base 与此时的元素交换

  • 此时 base 左边的元素全部小于它, 右边的元素全部大于它

  • 分别对左右数组重复执行以上步骤

5.2 核心代码:

int fenge(int a[], int left, int right) {
    int base = a[left];
    int temp;
    
    while (left < right) {
        // 先从右边开始找
        while (left < right && base <= a[right]) {
            right--;
        }
        // 再找左边的
        while (left < right && base > a[left]) {
            left++;
        }

        // 交换两个数在数组中的位置
        if (left < right) {
            temp = a[left];
            a[left] = a[right];
            a[right] = temp;
        }
    }

    // 基数归位
    a[left] = base;

    return left;
}

void quick_sort(int a[], int left, int right) {
    if (left < right) {
        int index = fenge(a, left, right);
        // 分别对左右两边数组进行快速排序
        quick_sort(a, left, index - 1);
        quick_sort(a, index + 1, right);
    }
}

5.3 算法分析

时间复杂度:

  • 最佳 T(n) = O(nlogn)

  • 最差 T(n) = O(n2)

  • 平均 T(n) = O(nlogn)


6. 桶排序 bucket sort

6.1 算法描述

  • 当待排序的数组值在一个明显的有限范围内(整型)时, 设计有限个有序桶

  • 将待排序的值装入对应的桶, 桶号就是待排序的值

  • 顺序输出各桶的值, 得到有序数列

6.2 核心代码:

#define MIN     0
#define MAX     100

int bucket[MAX - MIN] = {0,};

void bucket_sort(int a[], int n) {
    for (int i = 0; i < n; i++) {
        bucket[a[i]]++;
    }

    for (int i = 0; i < n; i++) {
        for(int j = MIN; j <= MAX; i++) {
            while (bucket[j]-- != 0) {
                a[i++] = j;
            }
        }
    }
}

6.3 算法分析

时间复杂度:

  • 最佳 T(n) = O(n+k) k 为 MAX - MIN

  • 最差 T(n) = O(n+k)

  • 平均 T(n) = O(n+k)


参考资料: https://blog.csdn.net/hellozhxy/article/details/79911867