原文:https://www.jianshu.com/p/876931436177
排序的相关概念
内排序是在排序整个过程中,带排序的所有记录全部放置在内存中。
根据排序过程中借助的主要操作,内排序分为:
外排序是由于排序的记录个数太多,不能同时放置在内存中,整个排序过程需要在内外存之间多次交换数据才能进行。
按照算法的复杂度分类
因为在冒泡排序中要用到顺序表结构和数组两元素的交换,先把这些写成函数
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
#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;
}
冒泡排序(Bubble Sort)是一种交换排序,它的基本思想是:两两比较相邻记录的关键字,如果反序则交换,直到没有反序的记录为止。
void BubblSort0(SqList *L){
int i,j;
for (i = 1; i < L->length; i++)
for (j = i+1; j <= L->length; j++)
if (L->r[i] > L->r[j])
swap(L, i, j);
}
对于这段代码,是最简单的冒泡,其实就是最简单的交换排序而已。它的思路就是让每一个关键字,都和它后面的每一个关键字比较,如果大则交换,这样第一位置的关键字在第一次循环后一定变成最小值。
假设我们待排序的关键字序列是{9,1,5,8,3,7,4,6,2}
i = 1
时,9与1交换后,在第一位置的1与后面的关键字比较都小,因此它就只最小值。i = 2
时,第二位置先后由9换成5,换成3,换成2,完成了第二小的数字交换。对于上面的算法,代码虽然简单易懂,但是效率非常低。可以改进成接下来的代码
void BubbleSort(SqList *L){
int i,j;
for (i = 1; i < L->length; i++)
for (j = L->length - 1; j >= i; j--)
if (L->r[j] > L->r[j+1])
swap(L, j, j+1);
}
假设我们待排序的关键字序列是{9,1,5,8,3,7,4,6,2}
i = 1
时,变量j由8反向循环到1,逐个比较,将较小值交换到前面,直到最后找到最小值放置在了第1的位置。i = 1
、 j = 8
时,6 > 2 ,因此交换了它们的位置,j = 7
时,4 > 2, 所以交换......直到j = 2
时,因为 1 < 2, 所以不交换。i = 2
时,变量j
由8反向循环到2,逐个比较,在将关键字2交换到第二位置的同时,也将关键字4和3有所提升。void BubbleSort1(SqList *L){
int i,j;
int 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;
}
}
}
}
#define N 9
int main(int argc, const char * argv[]) {
int i;
int d[N] = {9,1,5,8,3,7,4,6,2};
SqList l0;
for (i = 0; i < N; i++)
l0.r[i+1] = d[i];
l0.length = N;
printf("排序前:\n");
for (i = 0; i < l0.length; i++) {
printf("%d ", l0.r[i+1]);
}
printf("\n");
printf("1.0 初级冒泡排序结果:\n");
BubblSort0(&l0);
for (i = 0; i < l0.length; i++) {
printf("%d ", l0.r[i+1]);
}
printf("\n");
printf("1.1 冒泡排序结果:\n");
BubbleSort(&l0);
for (i = 0; i < l0.length; i++) {
printf("%d ", l0.r[i+1]);
}
printf("\n");
printf("1.2 优化后冒泡排序结果:\n");
BubbleSort1(&l0);
for (i = 0; i < l0.length; i++) {
printf("%d ", l0.r[i+1]);
}
printf("\n");
return 0;
}
测试结果
简单选择排序法(Simple Selection Sort)是通过n-i
次关键字间的比较,从n-i+1
个记录中选出关键字最小的记录,并和第i(1<=i<=n)个记录交换。
简单选择排序法的工作原理是:每一次从无序组的数据元素中选出最小(或最大)的一个元素,存放在无序组的起始位置,无序组元素减少,有序组元素增加,直到全部待排序的数据元素排完。
void SelectSort(SqList *L){
int i, j, min;
for (i = 1; i < L->length; i++) {
min = i;
for (j = i + 1; j <= L->length; j++) {
if (L->r[min] > L->r[j])
min = j;
}
if (i != min)
swap(L, i, min);
}
}
O(n^2)
。直接插入排序(Straight Insertion Sort)的基本操作是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录增1的有序表。
直接插入排序的核心思想:将一个记录插入到一个已经排序好的表中,以得到一个记录增加1的有序表。并且它把当前元素大的记录都往后移动,用以腾出“自己”该插入的位置。当n-1趟插入完成后该记录就是有序序列。
void InsertSort(SqList *L){
int i, j;
for (i = 2; i < L->length; i++) {
if (L->r[i] < L->r[i-1]) {
L->r[0] = L->r[i];
for (j = i-1; L->r[j] > L->r[0]; j++)
L->r[j+1] = L->r[i];
L->r[j+1] = L->r[0];
}
}
}
O(n^2)
。希尔排序是对直接插入排序的改进:
dlta[k] = 2^(t-k+1) - 1
时,可以获得不错的效果。希尔排序的核心思想:希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止
void ShellSort(SqList *L){
int i,j;
int increment = L->length;
do {
increment = increment /3 +1;
for (i = increment + 1; i < L->length; i++) {
if (L->r[i] < L->r[i-increment]) {
L->r[0] = L->r[i];
for (j = i - increment; i >0 && L->r[0] < L->r[j]; j -= increment)
L->r[j+increment] = L->r[j];
L->r[j+increment] = L->r[0];
}
}
} while (increment > 1);
}
O(n^(3/2))
,要好于直接插入排序的O(n^2);堆是具有如下性质的完全二叉树:
左边为大顶堆,右边为小顶堆
堆排序(Heap Sort)是利用堆(假设是大顶堆)进行排序。 堆排序的核心思想:
n-1
个序列重新构造成一个堆,这样就会得到n个元素的次小值。void HeadAdjust(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;
for (i = L->length / 2; i>0; i--)
HeadAdjust(L, i, L->length);
for (i = L->length; i > 1; i--) {
swap(L, 1, i);
HeadAdjust(L, 1, i-1);
}
}
HeapSort
中有两个for循环:i = L->length / 2
,i
从[9/2]=4
开始,4->3->2->1的变化量。HeadAdjust
的作用是将数组构建成一个大顶堆,在构建的时候利用了二叉树的性质。O(n)
,重建堆的时间复杂度为O(nlogn)
,所以总体来说堆排序的时间复杂度为O(nlogn)
,性能上远好于冒泡、简单选择、直接插入的时间复杂度。归并排序(Merging Sort)是利用归并的思想实现的。2路归并排序的核心思想如下:
n
个记录,则可以看成是n
个有序的子序列,每个子序列的长度为1,然后两两归并,得到n/2
个长度为2或者1的有序子序列n
的有序序列为止。#pragma - 6.归并排序(递归实现)
void Merge(int SR[], int TR[], int i, int m, int n){
int j, k, l;
for (j = m+1, k = i; i <= m && j <= n; k++) {
if (SR[i] < SR[j])
TR[k] = SR[i++];
else
TR[k] = SR[j++];
}
if (i <= m) {
for (l=0; l <= m-i; l++)
TR[k+l] = SR[i+l];
}
if (j <= n) {
for (l=0; l <= n-j; l++)
TR[k+l] = SR[j+l];
}
}
void MSort(int SR[], int TR1[], int s, int t){
int m;
int TR2[MAXSIZE+1];
if (s == t) {
TR1[s] = SR[s];
}else{
m = (s+t)/2;
MSort(SR, TR2, s, m);
MSort(SR, TR2, m+1, t);
Merge(TR2, TR1, s, m, t);
}
}
void MergeSort(SqList *L){
MSort(L->r, L->r, 1, L->length);
}
O(nlogn)
,并且这是归并排序算法中最好、最坏、平均的时间性能。O(n+logn)
用迭代实现的话,可以从最小的序列开始归并直到完成。
#pragma - 7.归并排序(迭代实现)
void MergePass(int SR[], int TR[], int s, int n){
int i = 1;
int j;
while (i <= n-2*s+1) {
Merge(SR, TR, i, i+s-1, i+2*s-1);
i = i+2*s;
}
if (i < n-s+1)
Merge(SR, TR, i, i+s-1, n);
else
for (j = i; j <= n; j++)
TR[j] = SR[j];
}
void MergeSort2(SqList *L){
int * TR = (int *)malloc(sizeof(L->length*sizeof(int)));
int k = 1;
while (k < L->length) {
MergePass(L->r, TR, k, L->length);
k = 2*k;
MergePass(TR, L->r, k, L->length);
k = 2*k;
}
}
log2n
的栈空间,空间只是用到申请归并临时用的TR
数组,因此空间复杂度为O(n)
.快速排序(Quick Sort)的基本思想是:
#pragma - 8.快速排序
int Partition(SqList * L, int low, int high){
int pivotkey;
pivotkey = L->r[low];
while (low < high) {
while (low < high && L->r[high] >= pivotkey)
high --;
swap(L, low, high);
while (low < high && L->r[low] <= pivotkey)
high++;
swap(L, low, high);
}
return low;
}
void QSort(SqList *L, int low, int high){
int pivot;
if (low < high) {
pivot = Partition(L, low, high);
QSort(L, low, pivot-1);
QSort(L, pivot+1, high);
}
}
void QuickSort(SqList *L){
QSort(L, 1, L->length);
}
Partition
函数就是将选取的pivotkey
不断交换,将比它小的换到它的左边,比它大的交换到它的右边,它也在交换中不断更改自己的位置,直到完全满足这个要求为止。O(nlogn)
。O(nlogn)
。pivotkey = L->r[low]
,即用序列的第一个元素作为枢轴,这是理想情况下 L->r[low]
是中间数。三数取中(median-of-three)法代码:
int pivotkey;
int m = low + (high - low)/2;
if (L->r[low] > L->r[high])
swap(L, low, high);
if (L->r[m] > L->r[high])
swap(L, high, m);
if (L->r[m] > L->r[low])
swap(L, m, low);
pivotkey = L->r[low];
int Partition1(SqList * L, int low, int high){
int pivotkey;
int m = low + (high - low)/2;
if (L->r[low] > L->r[high])
swap(L, low, high);
if (L->r[m] > L->r[high])
swap(L, high, m);
if (L->r[m] > L->r[low])
swap(L, m, low);
pivotkey = L->r[low];
L->r[0] = pivotkey;
while (low < high) {
while (low < high && L->r[high] >= pivotkey)
high--;
L->r[low] = L->r[high]
while (low < high && L->r[low] <= pivotkey)
low++;
L->r[high] = L->r[low];
}
L->r[low] = L->r[0];
return low;
}
void QSort1(SqList *L, int low, int high){
int pivot;
if ((high -low) > MAX_LINEGIH_INSERT_SORT) {
while (low < high) {
pivot = Partition1(L, low, high);
QSort1(L, low, pivot-1);
low = pivot+1;
}
}else
InsertSort(L);
}
void QuickSort1(SqList *L){
QSort1(L, 1, L->length);
}