数据结构–排序专题
数据结构–排序专题
于2020年11月18日2020年11月18日由Sukuna发布
1.插入排序
算法基本思想 将待排序的记录插入到已排序的子文件中去，使得插入之后得到的子文件仍然是有序子文件。插入一个记录，首先要对有序子文件进行查找，以确定这个记录的插入位置。按查找方式的不同，插入排序又可以分为线性插入排序和折半插入排序，前者使用顺序查找，后者使用折半查找。
1.1 简单插入排序
插入排序:设待排序的文件为：(r[1],r[2],…,r[n]) 关键字为：(r[1].key,r[2].key,…,r[n].key) 首先,将初始文件中的记录r[1]看作有序子文件； 第1遍：将r[2]插入有序子文件中，若： r[2].key<r[1].key， 则r[2]插在r[1]之前；否则，插在r[1]的后面。 第2遍：将记录r[3]插入前面已有2个记录的有序子文件中，得到3个记录的有序子文件。 以此类推，依次插入r[4],…,r[n],最后得到n个记录的递增有序文件。
就是找到最好的插入位置
void InsertSort(RecType r[],int n） // 对数组r[1..n]中的n个记录作插入排序 { int i,j； for (i=2；i<=n；i++){ r[0]=r[i]； //待插记录r[i]存入监视哨中 j=i-1； //以排序的范围1-i-1 //从r[i-1]开始向左扫描 while(r[0].key<r[j].key) { r[j+1]=r[j]； //记录后移 j–； //继续向左扫描 } r[j+1]=r[0]； //插入记录r[0],即原r[i] } }
(1)最好情况，原n个记录递增有序：比较关键字n-1次,移动记录2(n-1)次,(将数据复制到r[0]后又复制回来)(2)最坏情况:O(n^2)
1.2.折半插入排序（二分插入排序）
（a）由于插入排序的基本思想是在一个有序序列中插入一个新的记录，因此可以利用“折半查找”查询插入位置，由此得到的插入排序算法为“折半插入排序”，又被称为二分法插入排序。 （b）直接插入排序的算法简单易行，对长度(n)很大的记录序列宜采用性能更好的插入排序算法。 （c）折半插入排序过程中的折半查找的目的是查询插入点，因此不论是否存在和给定值相同的关键字，结束查找过程的条件都是high<low，并且插入位置为low指示的地方。
实例:插入到low处,low>high处停下
void BInsertSort (SqList &L) {
// 对顺序表L作折半插入排序
for ( i=2; i<=L.length; ++i )
{ //假定第一个记录有序
L.r[0] = L.r[i]; // 将L.r[i]暂存到L.r[0]
low = 1; high = i-1;
while (low<=high)
{ // 在r[low..high]中折半查找有序插入的位置
m = (low+high)/2; // 折半
if (L.r[0].key < L.r[m].key))
high = m-1; // 插入点在低半区
else
low = m+1; // 插入点在高半区
} // while
for ( j=i-1; j>=low; - -j ) L.r[j+1] = L.r[j]; // 记录后移 L.r[high+1] = L.r[0]; // 插入
} //for
} // BInsertSort1.3.希尔(shell)排序 (缩小增量排序)
（a）是插入排序中效率最高的一种排序方法。又称“缩小增量排序”，是由D.L.Shell在1959年提出来的。 （b）基本思想是，先对待排序列进行“宏观调整”，待序列中的记录“基本有序”时再进行直接插入排序。 注：所谓“ 基本有序” 是指，在序列中的各个关键字之前，只存在少量关键字比它大的记录。 （c）做法是：先取定一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组，所有距离为d1的倍数的记录放在同一个组中，在各组内进行直接插入排序；然后，到第二个增量d2<d1重复上述分组和排序，直至所取的增量dt=1（dt<dt-1<…<d2<d1），即所有记录放在同一组中进行直接插入排序为止。
例如·:3 2 1
1 4 5 3 2 6 3:三类:14 25 36 1 2 5 3 4 6 2:2类:135 246 1 2 4 3 5 6 1:一类:123456 1 2 3 4 5 6
2 交换排序
2.1 冒泡排序
基本思想: 设待排序的文件为r[1..n] 第1趟(遍)：从r[1]开始,依次比较两个相邻记录的关键字r[i].key和r[i+1].key,若r[i].key>r[i+1].key，则交换记录r[i]和r[i+1]的位置；否则,不交换。(i=1,2,…n-1) 第1趟之后,n个关键字中最大的记录移到了r[n]的位置上。 第2趟：从r[1]开始,依次比较两个相邻记录的关键字r[i].key和r[i+1].key,若r[i].key>r[i+1].key，则交换记录r[i]和r[i+1]的位置；否则,不交换。(i=1,2,…n-2) 第2趟之后,前n-1个关键字中最大的记录移到了r[n-1]的位置上。 …… 作完n-1趟,或者不需再交换记录时为止。
void bubble1(int a[],int n)
{ int i,j,temp；
for(i=0；i<n-1；i++) //作n-1趟排序
for(j=0；j<n-1-i；j++)
if (a[j]>a[j+1])
{ temp=a[j]； //交换记录
a[j]=a[j+1]；
a[j+1]=temp；
}
for(i=0；i<n；i++)
printf("%d",a[i])； //输出排序后的元素
}可以加一个swap变量,如果一次排序没换过元素,那就是
● 最好情况: 待排序的文件已是有序文件，只需要进行1趟 排序,共计比较关键字的次数为 n-1 不交换记录。 ● 最坏情况: 要经过n-1趟排序，所需总的比较关键字的次数为 (n-1)+(n-2)+…+1＝n(n-1)/2 交换记录的次数最多为 (n-1)+(n-2)+…+1＝n(n-1)/2 移动记录次数最多为 3n(n-1)/2 。 ● 只需要少量中间变量作为辅助空间。 O(1) ● 算法是稳定的。
2.2 快速排序
基本思想：首先在r[1..n]中，确定一个r[i]，经过比较和移动，将r[i]放到”中间”某个位置上，使得r[i]左边所有记录的关键字小于等于r[i].key，r[i]右边所有记录的关键字大于等于r[i].key。以r[i]为界,将文件划分为左、右两个子文件。 用同样的方法分别对这两个子文件进行划分, 得到4个更小的子文件。继续进行下去,使得每个子文件只有一个记录为止,便得到原文件的有序文件。
设置两个指针:一个大区域,一个小区域
void quksort(RecType r[],int low,int high)
{ RecType x；int i,j；
if (low<high) //有两个以上记录
{ i=low；j=high；x=r[i]； //保存记录到变量x中
do { //此时i指示位置可用
while (i<j && r[j].key>=x.key)
j--； //j从右向左端扫描通过key不小于x.key的元素
if (i<j) //i,j未相遇
{ r[i]=r[j]； i++； //此时j指示位置可用
while(i<j && r[i].key<=x.key)
i++； //i从左向右端扫描通过key不大于x.key的元素
if (i<j)
{ r[j]=r[i]；j--；}
}
} while (i!=j)； //i,j未相遇
}在上一级的函数就分治即可
找到左边第一个比20大的,右边第一个比20小的,交换位置
就平均速度而言，快速排序是已知内部排序方法中最好的一种排序方法,其时间复杂度为O(nlog_2n)。但是，在最坏情况下（基本有序时），快速排序所需的比较次数和冒泡排序的比较次数相同,其时间复杂度为O(n^2)。快速排序需要一个栈空间来实现递归。若每次划分均能将文件均匀分割为两部分，则栈的最大深度为|log_2n|+1，所需栈空间为O(log_2n),即空间复杂度 S(n)= O (log2n)快速排序是不稳定的。
ElementType Median3( ElementType A[], int Left, int Right )
{
int Center = (Left+Right) / 2;
if ( A[Left] > A[Center] )
Swap( &A[Left], &A[Center] );
if ( A[Left] > A[Right] )
Swap( &A[Left], &A[Right] );
if ( A[Center] > A[Right] )
Swap( &A[Center], &A[Right] );
/* 此时A[Left] <= A[Center] <= A[Right] */
Swap( &A[Center], &A[Right-1] ); /* 将基准Pivot藏到右边*/
/* 只需要考虑A[Left+1] … A[Right-2] */
return A[Right-1]; /* 返回基准Pivot */
}
void Qsort( ElementType A[], int Left, int Right )
{ /* 核心递归函数 */
int Pivot, Cutoff, Low, High;
if ( Cutoff <= Right-Left ) { /* 如果序列元素充分多，进入快排 */
Pivot = Median3( A, Left, Right ); /* 选基准 */
Low = Left; High = Right-1;
while (1) { /*将序列中比基准小的移到基准左边，大的移到右边*/
while ( A[++Low] < Pivot ) ;
while ( A[--High] > Pivot ) ;
if ( Low < High ) Swap( &A[Low], &A[High] );
else break;
}
Swap( &A[Low], &A[Right-1] ); /* 将基准换到正确的位置 */
Qsort( A, Left, Low-1 ); /* 递归解决左边 */
Qsort( A, Low+1, Right ); /* 递归解决右边 */
}
else InsertionSort( A+Left, Right-Left+1 ); /* 元素太少，用简单排序 */
}（52, 49, 80, 36, 14, 75, 58, 97, 23, 61） 经第1趟快速排序之后为： (23, 49, 14, 36) 52 (75, 58, 97, 80, 61) 经第2趟快速排序之后为： (14) 23 (49, 36) 52 (61, 58) 75 (80, 97) 经第3趟快速排序之后为： (14, 23, 36, 49, 52, 58, 61, 75, 80, 97) 注：为避免出现枢轴记录关键字为”最大”或”最小”的情况，通常进行的快速排序采用”三者取中”的改进方案，即以 R[s]、R[t] 和 R[(s+t)/2] 三者中关键字介于中值者为枢轴。只要将它和 R[s] 互换，一次划分的算法仍不变。
3 选择排序
3.1 简单选择
算法思想:设待排序的文件为(r[1],r[2],…,r[n]),关键字为(r[1].key,r[2].key,…,r[n].key), 第1趟(遍)：在(r[1],r[2],…,r[n])中,选出关键字最小的记录r[min].key，若min≠1,则交换r[1]和r[min]； 需要进行n-1次比较。 第2趟(遍)：在n-1个记录(r[2],…,r[n])中,选出关键字最小的记录r[min].key，若min≠2,则交换r[2]和r[min]； 需要进行n-2次比较。 第n-1趟(遍)：在最后的2个记录记录(r[n-1],r[n])中,选出关键字最小的记录r[min].key，若min≠n-1,则交换r[n-1]和r[min]；需要进行1次比较。
3.2 树形选择排序
树形选择排序又称锦标赛排序（Tournament Sort），是一种按照锦标赛的思想进行选择排序的方法。可用一棵有n个叶子结点的完全二叉树表示。 基本思想为： 首先对n个记录的关键字进行两两比较，然后在其中n/2个较小者之间再进行两两比较，如此重复，直到选出最小关键字的记录为止（树根）。 将最小关键字输出，且将其原来位置改为极大数，与此位置相关部分重新（向树根方向）进行比较，选出次小关键字，保留结果。 如此下去，直至全部排序完成。
$19_1,1,23,27,55,19_2,84,14$
该方法比直接选择排序速度上有很大提高，其缺点有： （1）需要另开储存空间保存排序结果； （2）n个待排序关键字，需要额外的（n-1）个内部结点（包括根结点），增加了内存开销。 （3）将最小关键字改为极大数，再与兄弟结点比较属于多余。 故：树形选择排序一般不是用来排序而是用来证明某些问题。为了弥补以上缺点，威洛姆斯在1964年提出了另一种形式的选择排序—堆排序。
3.3 堆排序
堆的定义略 问题1：如何将序列{k1,k2,…,kn} 处理成（大顶）堆（初始化）？ 问题2：如何在堆顶元素被替换后，调整剩余元素成为一个新的堆。
孩子比父亲大:最大的孩子和父亲交换,一直到没有孩子或者孩子都比父亲小
void Swap( ElementType *a, ElementType *b )
{
ElementType t = *a; *a = *b; *b = t;
}
void PercDown( ElementType A[], int p, int N )
{ /* 改编代码4.24的PercDown( MaxHeap H, int p ) */
/* 将N个元素的数组中以A[p]为根的子堆调整为最大堆 */
int Parent, Child;
ElementType X;
X = A[p]; /* 取出根结点存放的值 */
for( Parent=p; (Parent*2+1)<N; Parent=Child ) {
Child = Parent * 2 + 1;
if( (Child!=N-1) && (A[Child]<A[Child+1]) )
Child++; /* Child指向左右子结点的较大者 */
if( X >= A[Child] ) break; /* 找到了合适位置 */
else /* 下滤X */
A[Parent] = A[Child];
}
A[Parent] = X;
}
void HeapSort( ElementType A[], int N )
{ /* 堆排序 */
int i;
for ( i=N/2-1; i>=0; i-- )/* 建立最大堆 */
PercDown( A, i, N );
for ( i=N-1; i>0; i-- ) {
/* 删除最大堆顶 */
Swap( &A[0], &A[i] ); /* 见代码7.1 */
PercDown( A, 0, i );
}
}这个代码把问题1和问题2统一化了 时间复杂度:O(nlogn)
4 归并排序
归并的操作,就是两个指针,谁少就copy谁,最后就把剩下的元素copy过去
第一个想法: 每个子文件的长度从2,4,8一直递增
1.假如说:现在还剩下2s以上的空缺,就直接s和s互相互补即可 2.假如说:现在还剩下s-2s的空缺,就剩下的部分归并 3.假如说:现在还剩下0-s的空缺,就直接照抄
当然,还有一种写法就是找到最中间的一个元素,然后进行分化
/* 归并排序 - 递归实现 */
/* L = 左边起始位置, R = 右边起始位置, RightEnd = 右边终点位置*/
void Merge( ElementType A[], ElementType TmpA[], int L, int R, int RightEnd )
{ /* 将有序的A[L]~A[R-1]和A[R]~A[RightEnd]归并成一个有序序列 */
int LeftEnd, NumElements, Tmp;
int i;
LeftEnd = R - 1; /* 左边终点位置 */
Tmp = L; /* 有序序列的起始位置 */
NumElements = RightEnd - L + 1;
while( L <= LeftEnd && R <= RightEnd ) {
if ( A[L] <= A[R] )
TmpA[Tmp++] = A[L++]; /* 将左边元素复制到TmpA */
else
TmpA[Tmp++] = A[R++]; /* 将右边元素复制到TmpA */
}
while( L <= LeftEnd )
TmpA[Tmp++] = A[L++]; /* 直接复制左边剩下的 */
while( R <= RightEnd )
TmpA[Tmp++] = A[R++]; /* 直接复制右边剩下的 */
for( i = 0; i < NumElements; i++, RightEnd -- )
A[RightEnd] = TmpA[RightEnd]; /* 将有序的TmpA[]复制回A[] */
}
void Msort( ElementType A[], ElementType TmpA[], int L, int RightEnd )
{ /* 核心递归排序函数 */
int Center;
if ( L < RightEnd ) {
Center = (L+RightEnd) / 2;
Msort( A, TmpA, L, Center ); /* 递归解决左边 */
Msort( A, TmpA, Center+1, RightEnd ); /* 递归解决右边 */
Merge( A, TmpA, L, Center+1, RightEnd ); /* 合并两段有序序列 */
}
}
void MergeSort( ElementType A[], int N )
{ /* 归并排序 */
ElementType *TmpA;
TmpA = (ElementType *)malloc(N*sizeof(ElementType));
if ( TmpA != NULL ) {
Msort( A, TmpA, 0, N-1 );
free( TmpA );
}
else printf( "空间不足" );
}/* 归并排序 - 循环实现 */
/* 这里Merge函数在递归版本中给出 */
/* length = 当前有序子列的长度*/
void Merge_pass( ElementType A[], ElementType TmpA[], int N, int length )
{ /* 两两归并相邻有序子列 */
int i, j;
for ( i=0; i <= N-2*length; i += 2*length )
Merge( A, TmpA, i, i+length, i+2*length-1 );
if ( i+length < N ) /* 归并最后2个子列*/
Merge( A, TmpA, i, i+length, N-1);
else /* 最后只剩1个子列*/
for ( j = i; j < N; j++ ) TmpA[j] = A[j];
}
void Merge_Sort( ElementType A[], int N )
{
int length;
ElementType *TmpA;
length = 1; /* 初始化子序列长度*/
TmpA = malloc( N * sizeof( ElementType ) );
if ( TmpA != NULL ) {
while( length < N ) {
Merge_pass( A, TmpA, N, length );
length *= 2;
Merge_pass( TmpA, A, N, length );
length *= 2;
}
free( TmpA );
}
else printf( "空间不足" );
}5 基数排序
就是构建十个桶,按照个位,先按照各元素放入桶里. 接着再取出,按照0-9的顺序,接着是十位,接着是百位
/* 基数排序 - 次位优先 */
/* 假设元素最多有MaxDigit个关键字，基数全是同样的Radix */
#define MaxDigit 4
#define Radix 10
/* 桶元素结点 */
typedef struct Node *PtrToNode;
struct Node {
int key;
PtrToNode next;
};
/* 桶头结点 */
struct HeadNode {
PtrToNode head, tail;
};
typedef struct HeadNode Bucket[Radix];
int GetDigit ( int X, int D )
{ /* 默认次位D=1, 主位D<=MaxDigit */
int d, i;
for (i=1; i<=D; i++) {
d = X % Radix;
X /= Radix;
}
return d;
}
void LSDRadixSort( ElementType A[], int N )
{ /* 基数排序 - 次位优先 */
int D, Di, i;
Bucket B;
PtrToNode tmp, p, List = NULL;
for (i=0; i<Radix; i++) /* 初始化每个桶为空链表 */
B[i].head = B[i].tail = NULL;
for (i=0; i<N; i++) { /* 将原始序列逆序存入初始链表List */
tmp = (PtrToNode)malloc(sizeof(struct Node));
tmp->key = A[i];
tmp->next = List;
List = tmp;
}
/* 下面开始排序 */
for (D=1; D<=MaxDigit; D++) { /* 对数据的每一位循环处理 */
/* 下面是分配的过程 */
p = List;
while (p) {
Di = GetDigit(p->key, D); /* 获得当前元素的当前位数字 */
/* 从List中摘除 */
tmp = p; p = p->next;
/* 插入B[Di]号桶尾 */
tmp->next = NULL;
if (B[Di].head == NULL)
B[Di].head = B[Di].tail = tmp;
else {
B[Di].tail->next = tmp;
B[Di].tail = tmp;
}
}
/* 下面是收集的过程 */
List = NULL;
for (Di=Radix-1; Di>=0; Di--) { /* 将每个桶的元素顺序收集入List */
if (B[Di].head) { /* 如果桶不为空 */
/* 整桶插入List表头 */
B[Di].tail->next = List;
List = B[Di].head;
B[Di].head = B[Di].tail = NULL; /* 清空桶 */
}
}
}
/* 将List倒入A[]并释放空间 */
for (i=0; i<N; i++) {
tmp = List;
List = List->next;
A[i] = tmp->key;
free(tmp);
}
}6 计数排序
这个可以用于排序的数范围已知的情况,非常好写
7 排序算法的比较
腾讯云开发者
