当前位置:   article > 正文

数据结构——相关内部排序算法梳理_数据结构中,对排序数据的初始状态不作任何要求的排序算法

数据结构中,对排序数据的初始状态不作任何要求的排序算法

一、插入排序

1、直接插入排序

① 算法思想:直接插入于有序

初始序列:
49 38 65 97 76 13 27 49
第一个数49默认有序:
49 38 65 97 76 13 27 49
38:经过比较,38插入49之前
38 49 65 97 76 13 27 49
65:经过比较,不需要移动
38 49 65 97 76 13 27 49
97:同理,也不需要移动
38 49 65 97 76 13 27 49
76:经过比较,76插入到97之前
38 49 65 76 97 13 27 49
13:经过比较,13插入到38之前
13 38 49 65 76 97 27 49
27:经过比较,27插入到38之前
13 27 38 49 65 76 97 49
49:经过比较,49插入到65之前
13 27 38 49 49 65 76 97

② 算法实现

void insertSort(int R[], int n){
    int j; 
    int temp;
    for(int i = 1; i < n; i++){ 
        // i 标识待排序关键字下标,从第二个元素开始排,因为第一个默认有序
        temp = R[i]; // 将当前待插入关键字暂存下来
        j = i - 1; // j 默认是当前待插入关键字前面的关键字下标
        while(j >= 0 && temp < R[j]){
            R[j+1] = R[j];
            --j;
        } // 寻找插入位置,大的关键字依次向后移动
        R[j+1] = temp; // j在while循环里多减了1
    }   
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

2、折半插入排序

折半插入排序是对直接插入排序的一个优化,在排序过程的不断进行中,已排好序的元素会依次增多,后续的待元素在已排好序的序列中寻找其插入位置时,可通过折半查找减少比较次数(移动次数没有发生变化)。

① 算法思想

算法思想同直接插入排序,折半插入排序比较次数与初始状态无关:O(nlog2n);直接插入排序比较次数与初态有关:O(n)~O(n2)

② 算法实现

void binaryInsertSort(int R[], int n){
    int i, j, k; 
    int temp;
    int low, high;
    for(i = 1; i < n; i++){ 
        // i 标识待排序关键字下标,从第二个开始排,因为第一个默认有序
        temp = R[i];
        low = 0;
        high = i - 1;
        // 折半查找待插入的位置
        while(low <= high){
            k = (low+high)/2;
            if(R[k] > R[i]){
                high = k - 1;
            }else {
                low = k + 1;
            }
        }
        //将k到i位置的元素依次后移
        for(j = i; j > k + 1; j--){
            R[j] = R[j-1];
        }
        R[k+1] = temp;
    }   
}
  • 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

3、希尔排序

又叫缩小增量排序,希尔提出的(还有其他人提出的,思想相同)增量默认选取为序列长度n的一半⌊n/2⌋,再依次缩小增量为⌊n/4⌋…⌊n/2k⌋…,2,1,算法时间复杂度为O(n2)。当增量选取为1时,就是直接插入排序。

① 算法思想:希尔步长

初始序列:
49 38 65 97 76 13 27 49
➡️ 默认增量为4:
49 38 65 97 76 13 27 49
用了四种颜色标示出四个序列,分别对其进行直接插入排序:
49 13 27 49 76 38 65 97
➡️ 缩小为2:
49 13 27 49 76 38 65 97
用了两种颜色标示出两个序列,分别对其进行直接插入排序:
对红色:27 13 49 49 65 38 76 97
对蓝色:27 13 49 38 65 49 76 97
➡️ 缩小为1:
27 13 49 38 65 49 76 97
之后再直接插入排序:
27 13 49 38 65 49 76 97
13 27 49 38 65 49 76 97
13 27 49 38 65 49 76 97
13 27 38 49 65 49 76 97
13 27 38 49 49 65 76 97
13 27 38 49 49 65 76 97
13 27 38 49 49 65 76 97

② 算法实现


void shellSort(int R[], int n)
{
	int i, j, temp;
	int k = n / 2;
	while (k >= 1) {
		for (i = k; i < n; i++) {
			temp = R[i];
			j = i - k;
			while (R[j] < temp && j >= 0) {
				R[j+k] = R[j];
				j = j - k;
			}
			R[j+k] = temp;
		}
		k = k / 2;
	}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

二、交换排序

1、冒泡排序

从前往后,把大的往后换
i 记录当前一趟排序结束后,最大元素应该存储的位置
j 指示每一趟排序中的当前元素,当该元素比其前一个元素进行对比,如果前一个元素比该元素大,则交换位置,直到一趟比较完成

void BubbleSort(int R[], int len){
    int flag, temp;
    for(int i = len - 1; i >= 1; i-- ){
        flag = 0;
        for(int j = 1; j <= i; j++){
            if(R[j-1] > R[j]){
                temp = R[j];
                R[j] = R[j-1];
                R[j-1] = temp;
                flag = 1;
            }
        }
        if(flag == 0){ // 排序一趟若未发生交换,则证明序列有序,排序结束
            return;
        }
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

2、快速排序

取第一个元素作为枢轴元素,遍历后面的序列,依次比较,比枢轴元素的大的往后移动,比枢轴元素小的往前移动。
初始序列:
49 \color{red}{49} 49 38 65 97 76 13 27 49 ‾ \underline{49} 49
选第一个元素49作为枢轴元素,排序过程如下:
希尔排序过程
一趟排序结束:27 38 13 49 \color{red}{49} 49 76 97 65 49 ‾ \underline{49} 49
可以看出,一趟排序之后,初始序列被枢轴元素划分为两个子序列,分别再对两个子序列进行递归的快速排序,经过几趟之后,最终会得到有序序列。每趟排序对子序列的划分都是一次排序,这样一趟结束后就有一个关键字到达最终的位置。

void quickSort(int R[], int low, int high){
    int temp;
    int i = low; j = high;
    if(low < high){
        temp = R[low]; // 选定序列中第一个元素作为枢轴元素,并将该元素暂存下来
        while(i < j && R[j] >= temp){
            --j; // 从后往前找到第一个不小于枢轴元素的元素
        }
        if(i < j){
            R[i] = R[j]; // 将当前这个较小的元素往前换
            ++i; // i所在位置的元素已被覆盖,i后移一位,j指针暂停
        }
        while(i < j && R[i] < temp){
            ++i; // 同理,从前往后找到一个大于枢轴元素的元素
        }
        if(i < j){
            R[j] = R[i]; // 将当前这个较大的元素往后换
            --j; // j所在位置的元素已被覆盖,j前移一位,i指针暂停
        }
        R[i] = temp; // i,j两个指针相遇,将枢轴元素放入i,j指针所指的位置
        quickSort(R, low, i-1); // 再依次遍历枢轴元素左右的两个子序列
        quickSort(R, 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

三、选择排序

1、简单选择排序

将初始序列看作一个无序序列,每一轮遍历都是在这个无序序列中找出最小的元素,换到无序序列的第一个位置,不断重复操作,直到所有的元素有序。

① 算法思想

初始序列:
49 38 65 97 76 13 27 49
每趟找到最小的元素,黄色标示,与无序序列中第一个元素交换
第一趟(13和49交换):13 38 65 97 76 49 27 49
第二趟(27和38交换):13 27 65 97 76 49 38 49
第三趟(38和65交换):13 27 38 97 76 49 65 49
第四趟(49和97交换):13 27 38 49 76 97 65 49
第五趟(65和76交换):13 27 38 49 65 97 76 49
第六趟(49和97交换):13 27 38 49 65 49 76 97
此时序列已经有序,之后未发生交换

② 算法实现

void selectSort(int R[], int n){
    int k; // 保存最小的关键字
    int temp; // 暂存待交换的元素
    for(int i = 0; i < n; i++){
        k = i; // 取第一个元素作为默认的最小关键字
        // 从无序序列中挑选一个最小的关键字,重新作为 k 的值
        for(int j = i + 1; j < n; j++){
            if(R[k] > R[j]){
                k = j;
            }
        }
        // 将最小的关键字与 i 所指的位置的元素进行交换
        temp = R[i];
        R[i] = R[k]; // 一趟排序结束后,i 所指位置就保存了当前序列中最小的关键字
        R[k] = temp;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

每趟排序,总有一个元素落在其最终的位置上

2、堆排序

可以把堆看作一颗完全二叉树,并且满足:任何一个非叶结点的关键字不小于(或不大于)其左右子树的关键字。若父结点关键字大孩子关键字小,叫大根堆;否则成为小根堆;

① 算法思想

堆排序

② 算法实现

/**
* 实现数组R[low]到R[high]的范围内对在位置low上的结点进行调整
* 关键字存储设定为数组下标1开始
*/
void sift(int R[], int low, int high){
    int i = low, j = 2 * i; // R[j]是R[i]的左孩子结点 
    int temp = R[i];
    while(j <= high){
        if(j < high && R[j] < R[j+1]){ // 若右孩子较大,则把j指向右孩子
            ++j; // j 变为 2*i+1
        }
        if(temp < R[j]){ 
            R[i] = R[j]; // 将R[j]调整到双亲结点的位置上
            i = j;  // 修改 i 和 j 的值,以便继续向下调整
            j = 2 * i;
        }else{
            break; // 调整结束
        }
    }
    R[i]= temp; // 被调整结点的值放入最终位置
}
/* 堆排序函数 */
void heapSort(int R[], int n){
    int i;
    int temp;
    for(i = n/2; i >= 1; --i){
        sift(R, i, n); // 建立初始堆
    }
    for(i = n; i >= 2; --i){ // 进行 n-1 次循环,完成堆排序
       temp = R[1];
       R[1] = R[i];
       R[i] = temp; // 换出根结点的关键字,将其放入最终位置

       sift(R, 1, i-1); // 在减少了 1 个关键字的无序序列中进行调整
    }
}
  • 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

四、二路归并排序

1. 算法思想

初始序列:
49 38 65 97 76 13 27 49
两两归并,并排序
{49 38} {65 97} {76 13} {27 49}
{38 49} {65 97} {13 76} {27 49}
继续两两归并,并排序
{38 49 65 97} {13 76 27 49}
{38 49 65 97} {13 27 49 76}
最后剩两个子序列,再进行一次归并排序,即可完成
{13 27 38 49 49 65 76 97}

2. 算法实现

void mergeSort(int 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);
    }
}
/**
* 将low到mid和mid+1到high的两个有序序列合并成一个有序序列
*/
void merge(int A[], int low, int mid, int high){
    var temp;
    while(low < high){
        // 从前往后依次比较两个序列,将后面序列中较小元素往前换
        if(A[low] > A[mid+1]){
            temp = A[mid+1];
            // 其它元素后移
            for(var i = mid+1; i > low; --i){
                A[i] = A[i-1];
            }
            A[low] = temp;
            if(mid+1 < high){
                mid++;
            }
        }
        low++;
    }
}
  • 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

五、基数排序

1.算法思想

基于各位的大小进行排序的方法。通常有两种方法:一种是最高位优先(MSD)法,按关键字位权重递减依次进行排序;另一种是最低位优先(LSD)法,按关键字位权重递增依次进行排序;
通常采用链式基数排序,假设对如下10个记录进行排序:
在这里插入图片描述

各排序算法比较:

在这里插入图片描述

在这里插入图片描述

记忆口诀:

直接插入排序:直接插入于有序;
简单选择排序:选择最小于无序;
希尔排序:希尔步长,不断减半
快速排序:高速枢轴,基于分治
归并排序:分路排,再归并

☆☆☆一些重要结论:

  1. 经过一趟排序,总有一个关键字能到达最终位置,这样的排序是交换类冒泡、快速)和选择类简单选择、堆
  2. 排序过程中关键字的比较次数和初始序列无关折半插入、简单选择
  3. 排序过程中关键字的比较次数和初始序列有关直接插入、希尔、冒泡、 快速、堆排序
  4. 元素的移动次数与关键字的初始排列次序无关的是:基数排序
  5. 算法的时间复杂度与初始序列无关的是:选择排序、堆排序、归并排序、基数排序
  6. 排序过程中排序趟数与初始序列无关:插入类的排序(直接插入、折半插入、希尔排序)、简单选择排序、归并排序、基数排序
  7. 排序过程中排序趟数与初始序列有关:交换类的排序( 冒泡、快速)
  8. 快速排序,希尔排序,简单选择排序,堆排序都是不稳定排序,其他都是稳定排序
  9. 借助于“比较”进行排序的算法,在最坏情况下的时间复杂度至少为O(nlog2n)
  10. 当数据规模小时,宜采用直接插入、简单选择
  11. 当数据规模较大时,宜采用时间复杂度为O(nlog2n)的排序方法:快速、堆排序、归并排序
  12. 当关键字已基本有序,宜采用直接插入、冒泡排序
  13. 当数据规模较大时,宜采用快速排序,关键字分布随机,采用快速排序时间最短
  14. 堆排序所需的辅助空间比快速排序少,小根堆的关键字的最大记录在完全二叉树的结点⌊n/2 + 1⌋~n 中
  15. 归并排序依可以用于内排,也可用外排
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/寸_铁/article/detail/759049
推荐阅读
相关标签
  

闽ICP备14008679号