各种排序算法总结(C语言版)
6.1.1 冒泡排序
算法实例
21
25 49
25* 16
0
1
2
3
4
21 25 25* 16 08
08 5
49 chang=1
21 25 16 08 25* 49 chang=1
21 16 08 25 25* 49 chang=1
6.1.1 冒泡排序
算法实例
i=4
16 08
for(i=1;i<=10-j;i++) if(a[i]>a[i+1]) {t=a[i]; a[i]=a[i+1]; a[i+1]=t;}
printf("The sorted numbers:\n"); for(i=1;i<11;i++)
printf("%d ",a[i]); }
6.1.2 快速排序
6.1.3 直接插入排序
实用例子：
已知待序的一组记录的初始排列为：21, 25, 49, 25*, 16, 08
21 25 49 25* 16 08 012345
6.1.3 直接插入排序
实用例子：
i=1
21 25 49 25* 16 08 25 012345 temp
i=2 i=3
21 25 49 25* 16 08 49 012345 temp
6.1.2 快速排序
算法实例：
始关键字
pivotkey 21 25 low
49 25* 16 08 high
一次交换
21
二次交换
三次交换
high-1 完成一趟排序
08 25 low
49 25* 16
high
08
49 25* 16 25
low
high
08 16 49 25*
25
low
08 16
low
21 25 49 25* 16 08 25* 012345
6.1.3 直接插入排序
实用例子：
i=4
21 25 25* 49 16 08 16 0 1 2 3 4 5 temp
i=
16 21 25 25* 49 08 08
5
0 1 2 3 4 5 temp
完成
08 16 21 25 25* 49 01234 5
6.1.3 直接插入排序
算法实现：
void InsertSort (int r[ ], int n ) {
// 假设关键字为整型，放在向量r[]中 int i, j, temp; for (i = 1;i< n;i++ ) {
temp = r[i]; for(j = i;j>0;j- -) {//从后向前顺序比较，并依次后移
for i=1 to n-j
真
a[i]>a[i+1]
a[i]a[i+1]
输出a[1] 到 a[n]
#include <stdio.h> main() { int a[11],i,j,t;
printf("Input 10 numbers:\n"); for(i=1;i<11;i++)
scanf("%d",&a[i]); printf("\n"); 假 for(j=1;j<=9;j++)
if ( temp < r[j-1] ) r[j] = r[j-1];
else break;
} r[j] = temp; } }
6.1.3 直接插入排序
算法分析：
关键字比较次数和记录移动次数与记录关键字的初始排列有关。
最好情况下, 排序前记录已按关键字从小到大有序, 每趟只需与前面有序 记录序列的最后一个记录比较1次, 移动2次记录, 总的关键字比较次数 为 n-1, 记录移动次数为 2(n-1)在平均情况下的关键字比较次数和记录 移动次数约为 n2/4。
算法特点：
快速排序是通过比较关键码、交换记录， 以某个记录为界(该记录称为支点)，将待排序列分成两部分 一部分所有记录的关键码大于等于支点记录的关键码 另一部分所有记录的关键码小于支点记录的关键码
6.1.2 快速排序
算法描述：
任取待排序记录序列中的某个记录(例如取第一个记录)作为基准(枢),按照该记录的 关键字大小,将整个记录序列划分为左右两个子序列 左侧子序列中所有记录的关键字都小于或等于基准记录的关键字 右侧子序列中所有记录的关键字都大于基准记录的关键字 基准记录则排在这两个子序列中间(这也是该记录最终应安放的位置)。 然后分别对这两个子序列重复施行上述方法，直到所有的记录都排在相应位置上为 止。 基准记录也称为枢轴（或支点）记录。 取序列第一个记录为枢轴记录，其关键字为Pivotkey 指针low指向序列第一个记录位置 指针high指向序列最后一个记录位置
21
25
25*
49 chang=1
0
1
23
4
5
i=5
08
16
21
25
25*
49 chang=0
6.1.1 冒泡排序
算法实例
21
21
21
21
16
08
25
25
25
16
08
16
49
25
16
08
21
21
25
16
08
25
25
25
16
08
25
25
25
25
08
49
49
49
49
49
6.1.1 冒泡排序
算法实现
输入n 个数给a[1] 到 a[n] for j=1 to n-1
6.1.3 直接插入排序
操作细节：
当插入第i(i≥1)个对象时, 前面的r[0], r[1], …, r[i-1]已经排 好序。
用r[i]的关键字与r[i-1], r[i-2], …的关键字顺序进行比较(和顺 序查找类似)，如果小于，则将r[x]向后移动(插入位置后的记录向 后顺移)
找到插入位置即将r[i]插入
08 16
21
high 25* 49 25
high 25* 49 25
low high
ቤተ መጻሕፍቲ ባይዱ.1.2 快速排序
算法实例：
完成一趟排序
08 16
21 25* 49 25
分别进行快速排序 有序序列
08 16
21 25* 25 49
08 16
21 25* 25 49
9
6.1.2 快速排序
算法分析：
快速排序是一个递归过程; 利用序列第一个记录作为基准，将整个序列划分为左右两个子序列。只要 是关键字小于基准记录关键字的记录都移到序列左侧； 快速排序的趟数取决于递归树的高度。 如果每次划分对一个记录定位后, 该记录的左侧子序列与右侧子序列的长 度相同, 则下一步将是对两个长度减半的子序列进行排序, 这是最理想的情 况
10
6.1.3 直接插入排序
算法描述：
记录存放在数组R[0….n-1]中，排序过程的某一中间时刻，R被划分 成两个子区间R[0…i-1]和R[i….n-1]，其中：前一个子区间是已排好 序的有序区；后一个子区间则是当前未排序的部分。
基本操作
将当前无序区的第1个记录R[i]插入到有序区R[0….i-1]中适当的位置 ，使R[0…i]变为新的有序区