常见的排序算法
2020-05-19 本文已影响0人
_涼城
排序
排序的目的是将一组“无序”的记录序列调整为“有序”的记录序列。
若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。
反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。
#define MAXSIZE 10000
typedef int bool;
#define true 1;
#define false 0;
typedef struct
{
int r[MAXSIZE + 1];
int length;
}SqList;
//通用交换方法
void swap(SqList *L,int i,int j){
int temp = L->r[i];
L->r[i] = L->r[j];
L->r[j] = temp;
}
冒泡排序
冒泡排序重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成，理论上总共要进行n(n-1）/2次交换。
基本思想
两两比较相邻的记录的关键字，如果反序则交互，直到没有反序的记录为止。
代码实现
/*
冒泡排序
*/
void BubbleSort(SqList *L){
int i, j;
bool flag = true;
for (i = 1; i < L->length && flag; i++)
{
flag = false;
for (j = L->length - 1; j>= i; j--)
{
if (L->r[j] > L->r[j + 1])
{
swap(L,j,j+1);
flag = true;
}
}
}
}
选择排序
简单选择排序就是通过次关键词比较，从
个记录中找出关键字最小的记录，并和第i个记录进行比较。
代码实现
void SelectSort(SqList *L){
int i,j,min;
for (i = 1; i < L->length; i++) {
//① 将当前下标假设为最小值的下标
min = i;
//② 循环比较i之后的所有数据
for (j = i+1; j <= L->length; j++) {
//③ 如果有小于当前最小值的关键字,将此关键字的下标赋值给min
if (L->r[min] > L->r[j]) {
min = j;
}
}
//④ 如果min不等于i,说明找到了最小值,则交换2个位置下的关键字
if(i!=min)
swap(L, i, min);
}
}
直接插入排序
直接插入排序算法是将一个记录插入到已经排好序的有序表中，从而得到一个新的，记录数增1的有序表。
代码实现
void InsertSort(SqList *L){
int i,j;
int temp = 0;
for (int i = 2; i <= L->length;i++)
{
if (L->r[i] < L->r[i - 1])
{
temp = L->r[i];
for (j = i - 1; L->r[j] > temp; j--)
{
L->r[j + 1] = L->r[j];
}
L->r[j + 1] = temp;
}
}
}
希尔排序
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。该方法实质上是一种分组插入方法。
代码实现
void shellSort(SqList *L){
int i,j;
int increment = L->length;
//0,9,1,5,8,3,7,4,6,2
//① 当increment 为1时,表示希尔排序结束
do{
//② 增量序列
increment = increment/3+1;
//③ i的待插入序列数据 [increment+1 , length]
for (i = increment+1; i <= L->length; i++) {
//④ 如果r[i] 小于它的序列组元素则进行插入排序,例如3和9. 3比9小,所以需要将3与9的位置交换
if (L->r[i] < L->r[i-increment]) {
//⑤ 将需要插入的L->r[i]暂时存储在L->r[0].和插入排序的temp 是一个概念;
L->r[0] = L->r[i];
//⑥ 记录后移
for (j = i-increment; j > 0 && L->r[0]<L->r[j]; j-=increment) {
L->r[j+increment] = L->r[j];
}
//⑦ 将L->r[0]插入到L->r[j+increment]的位置上;
L->r[j+increment] = L->r[0];
}
}
}while (increment > 1);
}
堆排序
堆结构
堆结构是具有下面性质的完全二叉树；每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于等于其左右孩子的结点的值，称为小顶堆。
基本思想
- 将待排序的序列构成一个大顶堆，此时，整个序列的最大值就是堆顶的根结点，将它与堆数组的末尾元素交互，此时末尾元素就是最大值；
- 将剩下的n-1个序列重新构成一个堆，这样就会得到n个元素的次大值，重复执行，就能得到一个有序队列。
代码实现
void HeapAjust(SqList *L,int s, int m){
int temp,j;
temp = L->r[s];
for (j = 2 * s; j <= m; j *= 2)
{
if (j < m && L->r[j] < L->r[j+1])
{
++j;
}
if (temp >= L->r[j])
{
break;
}
L->r[s] = L->r[j];
s = j;
}
L->r[s] = temp;
}
void HeapSort(SqList *L){
int i;
//1.将现在待排序的序列构建成一个大顶堆;
//将L构建成一个大顶堆;
//i为什么是从length/2.因为在对大顶堆的调整其实是对非叶子的根结点调整.
for(i=L->length/2; i>0;i--){
HeapAjust(L, i, L->length);
}
//2.逐步将每个最大的值根结点与末尾元素进行交换,并且再调整成大顶堆
for(i = L->length; i > 1; i--){
//① 将堆顶记录与当前未经排序子序列的最后一个记录进行交换;
swap(L, 1, i);
//② 将L->r[1...i-1]重新调整成大顶堆;
HeapAjust(L, 1, i-1);
}
}
