排序总述

首先介绍链式和顺序存储的区别,经常搞混

线性表的顺序存储

又称顺序表,是用一组地址连续的存储单元依次存储线性表中的数据元素,从而使逻辑上相邻的元素在物理地址上也相邻,重点就是逻辑顺序与物理顺序相同.特点 为随机访问 , ,即可以通过首地址和元素序号找到该元素.数组就属于该类型.

链表

通过一组任意的存储单元来存储线性表中的数据元素,一个很大的不同就是,失去了随机访问的特性

插入排序

直接排序插入

前面的为有序序列,每次将元素插入有序序列之中,特点就是每次插完之后,前面插过的元素是有序的,但是不能保证最终顺序是否改变.

相同元素位置不会改变,因此是稳定的,同时适用顺序存储和链式存储

折半插入排序

和直接的区别在于,先折半查找到元素待插位置,减少了比较次数,但是和上面相比,移动次数仍未改变

同时也是稳定的,但是只适用于顺序存储

希尔排序

将原序列分为若干子表,每个子表的间隔为d个元素,然后对于这里面的子表进行直接插入排序,直到增量为1

因为有可能相同的关键词被划分成不同的子表范围,因此是不稳定的,同时需要随机取到相隔为d的元素,因此,也只适用于顺序存储

交换排序

冒泡排序

从后向前,两两比较相邻的元素,若为逆序则交换他们.序列的变化为每次将待排的元素最小的前移到最前面位置,其余元素相对顺序不变.

如果相等就不会发生交换,因此是稳定的排序,同时适用与链式与顺序存储的线性表

快速排序

基本思想来自分治法,在待排序中选择一个枢轴,然后检索剩余元素,将所有小于该枢轴的放到前部分,大于等于的放到后部分,需要注意的是每次枢轴将序列分成两部分,因此在递归操作时,需要将这两部分在进行一次选择枢轴和划分,这称之为一趟.目前是所有排序算法当中平均性能最优的.

在划分时,如果右端存在两个关键字相同,而且小于基准值,则在交换完后相对位置会改变,因此不是稳定排序,同时需要从前向后,和从后向前进行遍历,因此不适合链式(那双向链表应该可以吧)

选择排序

简单选择排序

每一趟选择一个待排序列中的最小值,跑n-1趟自然就排好了

由于代码中写的是寻找 这种挑选是不能保证稳定的,假如加上等于号,每次挑选最小且最靠前的元素即可保证稳定性,因代码而异(稳定与否是可以自己控制的).因为没有涉及随机访问,因此适用与顺序和链式存储

堆排序

将所有元素构建成一棵完全二叉树,大顶堆或者小顶堆,(类似优先队列的实现),需要关注的有两点,一是如何建立初始堆,二是每次输出一个值后,该如何维护该堆的性质不发生变化.

筛选时,有可能把相同关键字的元素调整到前面,因此是不稳定的.需要 只适合顺序存储的

归并排序

将两个有序表合并成一个新的有序表,初始可认为有n个有序的子表,长度为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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <bits/stdc++.h>
using namespace std;

vector<int> vi;
int n = 10;
int A[10] = {1,2,8,9,3,4,5,6,7,10};
void print(){
    for(int i = 0;i<10;i++)
    {
        cout << A[i] <<" ";
    }
    cout << "\n";
}
/*
插入排序 每次将待排序的记录插入前面已经排好序的子序列
直接插入
折半插入 
希尔排序
*/
// 简单插入排序 令i从2到n枚举 将需插入元素在前面有序序列找到一个合适的位置 
// 插入进去 然后讲其后面元素后移一位
void insertSort(){
    
    for(int i = 2; i< n;i++){
        int temp = A[i];
        int j = i;
        while(j > 1 && temp < A[j-1]){ // 只要temp小于前一个元素A[j-1]
            A[j] = A[j-1];
            j--;
        }
        A[j] = temp;
    }
}

/*
交换排序主要有 冒泡和快排
交换排序是指根据序列中两个关键字的比较结果来对换这两个记录在序列中的位置
其中快排的基本思想为分治法 是所有内部排序算法中时间最优的算法
*/
// 简单选择排序 从1遍历到n,每趟操作从待排序选择最小的元素,令其与待排序部分的第一个元素交换
// 这个选择排序 也称为冒泡排序
void bubbleSort(){
    // 跑n趟 每次找到[i~n]的最小值
    for(int i = 0;i<n;i++){
        int k = i;
        for(int j = i;j<n;j++){ // 找出最小元素的下标
            if(A[j]<A[k]){
                k = j;
            }
        }
        swap(A[k],A[i]);
    }
}

// 快排 每次选择一个pivot 然后以该数字可以将区间分为两部分
// 思想为分治法 因此需要递归实现
int part(int low, int high){
    int pivot = A[low];// 默认枢轴为第一个元素
    
    // 双指针的思想 将区间划分成两部分 其中中间的那个就是枢轴
    while (low < high){
        while(low < high && A[high] >= pivot) --high;
        A[low] = A[high];
        while(low < high && A[low] <= pivot) ++low;
        A[high] = A[low];
    }
    A[high] = pivot; //此时的high应该与low相等
    return high;
}

void quickSort(int low, int high){
    if(low >= high) return;
    
    int pivotPos = part(low,high);// 划分出来中间位置
    quickSort(low, pivotPos-1);
    quickSort(pivotPos+1, high);
}

/*
选择排序
思想为每一趟的 如第i趟 在后面n-i+1个待排元素中选取关键字最小的元素
作为有序子序列的第i个元素 直到n-1趟排序后 待排元素只剩下一个元素
分为简单排序和堆排序
*/

// 简单选择排序 每次在后面选一个最小的放到前面去
// 可以看做 每次都选一个最小值放到前面
void selectSort(){
    for(int i = 0;i<n;i++){
        int min = i;//记录最小元素的位置即可
        for (int j = i;j<n;j++){
            if(A[j]<A[min]) min = j;
        }
        swap(A[i],A[min]);// 交换位置
    }
}

// 堆排序 
/*
堆是满足L[i] >= L[2*i] && L[i]>=L[2*i+1]
也可以视为完全二叉树 因为上面的元素关系和完全二叉树的表示一致
而且大根堆是最大元素放在顶点 且任意一个非根节点一定小于等于双亲节点
有两个问题 1.如何将初始无序序列构造成初始堆 2.输出栈顶元素 如何将剩余元素调整成新堆
*/
// 向下调整 将当前节点V和左右孩子进行比较 假如孩子存在权值比V大的 就交换彼此节点
// 这时候V到了下一层节点了 还需要比较此时的V和其孩子节点 如果还有大的也需要交换
// 直到V不小于其所有孩子节点
// 对数组在[low, high]调整 
// low为欲调整节点的数组下标 high是堆的最后一个数组下标
void downAdjust(int low, int high){
    int i = low, j = 2*i + 1 ;//i为欲调整节点 j为其孩子节点 具体的下标情况根据数组范围来
    while(j <= high){//存在孩子节点
        if(j+1 <= high && A[j+1] > A[j]){// 存在右孩子 且大于左孩子
            j++;
        }
        // 此时的j为最大的孩子下标 进行比较
        if(A[j] > A[i]){
            swap(A[i],A[j]);
            i = j; // i为欲调整节点 j为其孩子节点
            j = 2*i+1;
        }else{
            break;
        }
    }
}

void createHeap(){
    for(int i = n/2+1;i>=0;i--){
        downAdjust(i,n-1);
    }
}

void heapSort(){
    createHeap();
    for(int i = n-1;i>0;i--){
        cout << A[0] <<" ";
        swap(A[i],A[0]);
        downAdjust(1,i-1);
    }
}

int main()
{
    // insertSort();
    // bubbleSort();
    // quickSort(0,9);
    // selectSort();
    heapSort();
    // print();
    return 0;
}

堆排序

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

// 堆排序 
/*
堆是满足L[i] >= L[2*i] && L[i]>=L[2*i+1]
也可以视为完全二叉树 因为上面的元素关系和完全二叉树的表示一致
而且大根堆是最大元素放在顶点 且任意一个非根节点一定小于等于双亲节点
有两个问题 1.如何将初始无序序列构造成初始堆 2.输出栈顶元素 如何将剩余元素调整成新堆
*/
// 向下调整 将当前节点V和左右孩子进行比较 假如孩子存在权值比V大的 就交换彼此节点
// 这时候V到了下一层节点了 还需要比较此时的V和其孩子节点 如果还有大的也需要交换
// 直到V不小于其所有孩子节点
// 对数组在[low, high]调整 
// low为欲调整节点的数组下标 high是堆的最后一个数组下标

void downAdjust(int low, int high){
    int i = low, j = 2*i ;//i为欲调整节点 j为其孩子节点 
    
    while(j <= high){//存在孩子节点
        if(j+1 <= high && A[j+1] > A[j]){// 存在右孩子 且大于左孩子
            j++;
        }
        // 此时的j为最大的孩子下标 进行比较
        if(A[j] > A[i]){
            swap(A[i],A[j]);
            i = j; // i为欲调整节点 j为其孩子节点
            j = 2*i;
        }else{
            break;
        }
    }
}

void createHeap(){
    for(int i = n/2;i>=1;i--){
        downAdjust(i,n);
        // printf("调整的是节点:%d\n",i);
        // print();
    }
}

void heapSort(){
    createHeap();
    for(int i = n;i>0;i--){
        cout << A[1] <<" ";
        swap(A[i],A[1]);
        downAdjust(1,i-1);
    }
}
// 假如要删除堆顶元素 只需要让最后一个节点覆盖堆顶元素 然后下调根节点
void deleteTop(){
    A[1] = A[n--];
    downAdjust(1,n);
}

// 添加新的元素 把待添加元素放入数组最后 然后进行向上调整
// 向上调整是把调整节点和父亲节点比较 如果权值比父亲大 就交换彼此节点
// 因为作为堆 要记住最大的性质 每个节点是以其为根节点的子树中权值最大的节点
void upAdjust(int low,int high){
    int i = high,j = i / 2; // i为欲调整节点 j为父亲
    while(j >= low){
        if(A[j] < A[i]){
            //父亲太小了
            swap(A[j],A[i]);
            i = j;
            j /= 2;
        }else{
            break;
        }
    }
}

// 在堆中插入元素x
void insertHeap(int x){
    A[++n] = x;
    upAdjust(1,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
/*
利用递归写法
实际上每次都是和孩子比较 如果孩子比当前节点就交换
并且再去判断孩子 以孩子为目标 看看他的孩子有没有比他大的
最优子结构 当前为根的子树的所有节点都比根节点的权值小
换句话说 当前根节点为该子树最大的节点
如果调整了其孩子 就有可能造成子结构打乱 因此需要递归调整其孩子
*/
void downDie(int u){
    int zi = u * 2;//表示孩子节点
    if(u*2>n) return;// 没有孩子就退出
    if(zi + 1 <=n && A[zi] < A[zi+1]){
        zi++;
    }
    if(A[zi] > A[u]){
        swap(A[zi],A[u]);// 孩子比他大 交换 递归判断其孩子情况
        downDie(zi);
    }
}

// 同时 上调也有递归写法 适用与添加数据的情况
void upDie(int u){
    if(u<1) return; 
    int fa = u/2;//父亲只有一个

    // 父亲小了 让孩子上来
    if(A[fa] < A[u]){
        swap(A[fa],A[u]);
        upDie(fa);// 重新对这个新父亲开始调整
    }
}
专业课 > 数据结构 > 排序
#总结 #数据结构 #排序
排序总述
https://rain_dew.gitee.io/2024/07/16/专业课/数据结构/8.排序/排序总述/
Author
Wang yulu
Posted on
July 16, 2024
Licensed under