诚城的成长
诚城
2022-01-18
目录

排序原创

将无顺序的数字，按照一定规则进行排序。
分类：插入排序、交换排序、选择排序、归并排序。

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

不稳定是指2个相等的元素，位置可能会发生变化。

# 插入排序

# 直接插入排序

void InsertSort(ElementType a[], int n){
    int j;
    for (int i = 2; i < n;i++) { // 0下标作为哨兵暂存对比的数据，因此需要从2下标开始进行对比
        if(a[i] < a[i-1]){ // 如果当前下标的值 比 前下标的值小
            a[0] = a[i]; // 将当前下标的值存到哨兵
            for (j = i-1; a[0] < a[j] ; --j) { // 将已经排序好的顺序与哨兵进行对比，从末端进行比较
                a[j+1] = a[j]; // 有序数组后移一位，并替换当前比较位置的数据。
            }
            a[j+1]=a[0]; // 将哨兵位置的值替换到有序数组的对应位置
        }
    }
}

时间复杂度：外层循环 n次，内存循环n-1次，因此为 。
最好情况即数组本身就是有序的，因此仅循环了外层。

# 折半插入排序

仅减少了比较元素的次数，月为

笔记

时间复杂度为 。
外出循环 n 次，内存移动n+1次，所以为 。

void MinInsertSort(ElementType a[],int n){
    int low,hight,mid;
    for (int i = 2; i <= n ; i++) {
        a[0] = a[i];
        low =1; // 有序队列的头
        hight = i-1; // 有序队列的尾
        while( low <= hight){
            mid = (low+ hight)/2;
            if(a[mid] > a[0]){ // 二分定位，然后修改 low 或 hight 位置
                hight = mid - 1; //
            }else{
                low = mid + 1;
            }
        }
        for (int j = i-1; j < hight+1; --j) {
            a[j+1]=a[j]; // 同直插替换原理
        }
        a[hight+1] = a[0]; // 同直插替换原理
    }
}

# 希尔排序

「步长」= n/2。

警告

希尔排序编写复杂，而且时间复杂度相对快排、堆排没有优势，工业没有应用。

# 交换排序

# 冒泡排序

从后往前(或从前往后)两两比较相邻的两个元素大小，将小(或大)值不断迁移，直至最终所有数据按顺序排列。

void swap(ElementType &a, ElementType &b){
    ElementType temp;
    temp = a;
    a=b;
    b=temp;
}
// 冒泡排序
void BubbleSort(ElementType a[], int n){
    int tag;
    for (int i = 0; i < n-1; i++) {
        tag = 0;
        for (int j = n-1; j > 0 ; j--) {
            if(a[j-1] > a[j]){
                swap(a[j-1],a[j]);
            }
            tag=1; // 发生排序改变 标记
        }
        if(tag == 0) // 全部排完，提前结束
            break;
    }
}

# 快速排序 *重点

利用分治思想。以某个值作为标杆，将数组分成2半，然后将新数组各自递归。时间复杂度减一半。

int Partition(ElementType a[], int left, int right){
    int i,k;
    for (i = k=left; i < right; i++) {
        if(a[i] < a[right-1]){
            swap(a[i],a[k]);
            k++;
        }
    }
    swap(a[k],a[right-1]);
    return k;
}
void QuickSort(ElementType a[],int low,int high){
    if(low < high){
        int pivotpos = Partition(a,low,high);
        QuickSort(a,low,pivotpos-1);
        QuickSort(a,pivotpos+1,high);
    }
}

QuickSort部分不断的除2，要除n次，因此为；Partition总共要执行n次。因此时间复杂度为 。

  • 最坏情况即，数组本身有序。为解决这个问题，可随机抽取数组中任意一个值与最右边的值进行交换。
  • 空间复杂度，因为使用了递归，占用空间。

# 选择排序

# 简单选择排序

每一趟排序确定一个元素(本趟最小值)的最终位置，经过n-1趟排序就可以得到整个有序的排序表。

  • 时间复杂度同冒泡排序。但是交换的次数变少。

# 堆排序 *重点

需要掌握二叉树层次建树。
『堆』即用数组表示二叉树的层次建树的结构。堆也是一种数据结构。

笔记

层次建树完后一定是完全二叉树。
最后一个父结点的数组下标为n/2-1。
所有左子结点数组下标的规律：2*父结点+1。所有右子结点数组下标的规律：左结点+1。

# 大根堆

# 归并排序

递归的思想。两两成组，组成有序的数组，然后将有序数组在两两归并。

void Merge(ElementType a[], int low, int mid, int hight) {
    int n = 10;
    ElementType temp[10]; //是需要额外定义一个数组，为了降低操作次数
    for (int i = low; i <= hight; i++) { //改成 i = low; i <= hight; i++
        temp[i] = a[i];
    }
    int i, j, k;
    for (i = low, j = mid + 1, k = i; i <= mid && j <=hight; k++) {  //改成i <= mid && j <=hight
        if (temp[i] <= temp[j]) {
            a[k] = temp[i++]; // 等价于 a[k]=temp[i]; i++;
        }
        else {
            a[k] = temp[j++];
        }
    }
    while (i <= mid) {  // 当存在 低部分 还有未比对的值时
        a[k++] = temp[i++];
    }
    while (j <= hight) { // 当存在 高部分 还有未比对的值时
        a[k++] = temp[j++];
    }

}
// 归并排序
void MergeSort(ElementType a[], int low, int high){
    if(low < high){
        int mid = (low+high)/2;
        MergeSort(a,low,mid);
        MergeSort(a,mid+1,high );
        Merge(a,low,mid,high );
    }
}

时间复杂度：

  • MergeSort不断的除2，要除n次，因此为；
  • Merge执行n次。
  • 因为有使用额外数组，数组长度为n，因此空间复杂度为O(n)。

# 排序实例

::: datials

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h> // 用于生成随机数

typedef int ElementType;
typedef struct{
    ElementType *array; // 存储元素的起始地址
    int length;  // 统计元素个数
}SStable;

void ST_Inits(SStable &st,int length){
    st.length = length;
    st.array = (ElementType *) malloc(sizeof(ElementType)*st.length);
    srand(time(NULL)); // 生成随机数，引入 time.h
    for (int i = 0; i < st.length; i++) {
        st.array[i] = rand()%100; // 生成小于100 的整数
    }
}
void print_ST(SStable st){
    if(st.length == 0 ){
        printf("暂无数据！\n");
    }
    for (int i = 0; i < st.length; ++i) {
        printf("%3d",st.array[i]);
    }
    printf("\n");
}

void swap(ElementType &a, ElementType &b){
    ElementType temp;
    temp = a;
    a=b;
    b=temp;
}
// 冒泡排序
void BubbleSort(ElementType a[], int n){
    int tag;
    for (int i = 0; i < n-1; i++) {
        tag = 0;
        for (int j = n-1; j > 0 ; j--) {
            if(a[j-1] > a[j]){
                swap(a[j-1],a[j]);
            }
            tag=1; // 发生排序改变 标记
        }
        if(tag == 0) // 全部排完，提前结束
            break;
    }
}
// 快排分割
int Partition(ElementType a[], int left, int right){
    int i,k;
    for (i = k=left; i < right; i++) {
        if(a[i] < a[right-1]){
            swap(a[i],a[k]);
            k++;
        }
    }
    swap(a[k],a[right-1]);
    return k;
}
// 快速排序
void QuickSort(ElementType a[],int low,int high){
    if(low < high){
        int pivotpos = Partition(a,low,high);
        QuickSort(a,low,pivotpos-1);
        QuickSort(a,pivotpos+1,high);
    }
}
// 直接插入排序，从小到大排序，升序
void InsertSort(ElementType a[], int n){
    int j;
    for (int i = 2; i < n;i++) { // 0下标作为哨兵暂存对比的数据，因此需要从2下标开始进行对比
        if(a[i] < a[i-1]){ // 如果当前下标的值 比 前下标的值小
            a[0] = a[i]; // 将当前下标的值存到哨兵
            for (j = i-1; a[0] < a[j] ; --j) { // 将已经排序好的顺序与哨兵进行对比，从末端进行比较
                a[j+1] = a[j]; // 有序数组后移一位，并替换当前比较位置的数据。
            }
            a[j+1]=a[0]; // 将哨兵位置的值替换到有序数组的对应位置
        }
    }
}
// 折半插入
void MinInsertSort(ElementType a[],int n){
    int low,high,mid;
    for (int i = 2; i <= n ; i++) {
        a[0] = a[i];
        low =1; // 有序队列的头
        high = i-1; // 有序队列的尾
        while( low <= high){
            mid = (low+ high)/2;
            if(a[mid] > a[0]){ // 二分定位，然后修改 low 或 high 位置
                high = mid - 1; //
            }else{
                low = mid + 1;
            }
        }
        for (int j = i-1; j < high+1; --j) {
            a[j+1]=a[j]; // 同直插替换原理
        }
        a[high+1] = a[0]; // 同直插替换原理
    }
}
// 希尔排序
void shellSort(ElementType a[],int n){
    for (int dk=n/2;dk>=1;dk=dk/2) { //步长变化设计
        for (int i = dk+1; i <=n ; ++i) {
            if(a[i] < a[i-dk]){
                a[0]=a[i];
                int j;
                for (j = i-dk; j >0 && a[0] < a[j] ; j=j-dk) {
                    a[j+dk]=a[j];
                }
                a[j+dk]=a[0];
            }
        }
    }
}
// 简单选择排序
void SelectSort(ElementType a[],int n){
    int min;
    for (int i = 0; i < n-1; i++) { // 最多为
        min = i;
        for (int j = i+1; j < n; j++) {
            if(a[j] < a[min]){
                min = j;
            }
        }
        if(min != i){
            swap(a[i],a[min]);
        }
    }
}
// 建立大根堆
void AdjustDown(ElementType a[], int d, int len){
    int dad = d; // 结点
    int son = 2 * dad +1; // 左子结点
    while (son < len){ //
        if(son+1 < len && a[son] < a[son+1]){ // son+1 右结点，判断是否存在右结点
            son++;
        }
        if(a[son] > a[dad]){ // 子结点大于父节点 交换
            swap(a[son],a[dad]); // 子结点中大的值与父节点值交换。
            dad = son;    // 交换后，调整位置，便于进行下一步调整
            son=2*dad+1; // 交换后，调整位置，便于进行下一步调整
        }else{
            break;
        }
    }

}
//堆排序
void HeapSort(ElementType a[],int len){
    // 建立大根堆
    for (int i = len / 2 -1; i >=0 ; i--) { // len / 2 -1 获取到最后一个父节点
        AdjustDown(a,i,len);
    }
    swap(a[0],a[len-1]); // 交换 顶部与最后一个结点的数据
    for (int i = len-1; i > 0 ; i--) {
        AdjustDown(a,0,i);// 继续调整剩下元素为大根堆
        swap(a[0],a[i-1]); //交换 顶部与未替换元素的数据
    }
}
void Merge(ElementType a[], int low, int mid, int hight) {
    int n = 10;
    ElementType temp[10]; //是需要额外定义一个数组，为了降低操作次数
    for (int i = low; i <= hight; i++) { //改成 i = low; i <= hight; i++
        temp[i] = a[i];
    }
    int i, j, k;
    for (i = low, j = mid + 1, k = i; i <= mid && j <=hight; k++) {  //改成i <= mid && j <=hight
        if (temp[i] <= temp[j]) {
            a[k] = temp[i++]; // 等价于 a[k]=temp[i]; i++;
        }
        else {
            a[k] = temp[j++];
        }
    }
    while (i <= mid) {  // 当存在 低部分 还有未比对的值时
        a[k++] = temp[i++];
    }
    while (j <= hight) { // 当存在 高部分 还有未比对的值时
        a[k++] = temp[j++];
    }

}
// 归并排序
void MergeSort(ElementType a[], int low, int high){
    if(low < high){
        int mid = (low+high)/2;
        MergeSort(a,low,mid);
        MergeSort(a,mid+1,high );
        Merge(a,low,mid,high );
    }
}
void PrintLine(){
    printf("-----------------------------------------------------\n");
}
int main() {
    SStable ST;
    ST_Inits(ST,10); //使用随机数

    ElementType A[10]={12,63,58,95,41,35,65,0,38,44}; // 制定数组内容
    memcpy(ST.array,A, sizeof(A)); // 复制 整型数组、浮点型数组不能使用 strcpy 只能是用那个 memcpy，一个字节一个字节的复制
    printf("10个随机数据如下：\n");
    print_ST(ST);
    PrintLine();
    printf("冒泡排序后内容如下：\n");
    BubbleSort(ST.array,ST.length);
    print_ST(ST);
    PrintLine();
    printf("快排后内容如下：\n");
    QuickSort(ST.array,0,ST.length);
    print_ST(ST);
    PrintLine();
    printf("直接插入排序后内容如下：\n");
    InsertSort(ST.array,ST.length);
    print_ST(ST);
    PrintLine();
    printf("选择排序后内容如下：\n");
    SelectSort(ST.array,ST.length);
    print_ST(ST);
    PrintLine();
    printf("堆排后内容如下：\n");
    HeapSort(ST.array,ST.length);
    print_ST(ST);
    PrintLine();
    printf("归并排序后内容如下：\n");
    MergeSort(ST.array,0,ST.length-1);
    print_ST(ST);


    return 0;
}

:::

上次更新: 2022/08/23, 18:12:45
查找
图

← 图→

Theme by Vdoing | Copyright © 2022-2022 carveybunt | MIT License
×
×

特别申明：

本站所有内容均为个人理解或转载，如有不当之处，敬请大佬指导！