目录
一、排序的原理
一、排序的定义
插入排序：
交换排序：
二、快速排序的实现
d13作业：
一、排序的原理
一、排序的定义
稳定排序和非稳定排序
设文件f=（R1……Ri……Rj……Rn）中记录Ri、Rj（i≠j，i、j=1……n）的key相等，即Ki=Kj。
若在排序前Ri领先于Rj，排序后Ri仍领先于Rj，则称这种排序是稳定的，其含义是它没有破坏原本已有序的次序。
内排序和外排序
若待排文件f在计算机的内存储器中，且排序过程也在内存中进行，称这种排序为内排序。
若排序中的文件存入外存储器，排序过程借助于内外存数据交换（或归并）来完成，则称这种排序为外排序。
各种内排序方法可归纳为以下五类：
（1）插入排序
（2）交换排序
（3）选择排序
（4）归并排序
......
插入排序：
直接插入排序 折半插入排序 链表插入排序 Shell（希尔）排序 ……
直接插入排序：设待排文件f=（R1 R2……Rn）相应的key集合为k={k1 k2……kn}，
排序方法
先将文件中的（R1）看成只含一个记录的有序子文件，然后从R2起，逐个将R2至Rn按key插入到当前有序子文件中，最后得到一个有序的文件。插入的过程上是一个key的比较过程，即每插入一个记录时，将其key与当前有序子表中的key进行比较，找到待插入记录的位置后，将其插入即可。
折半插入排序：排序算法的T(n)=O(n2),是内排序时耗最高的时间复杂度。
折半插入排序方法
先将（R[1]）看成一个子文件，然后依次插入R[2]……R[n]。但在插入R[i]时，子表[R[1]……R[i-1]]已是有序的，查找R[i]在子表中的位置可按折半查找方法进行，从而降低key的比较次数。
链表插入排序：设待排序文件f=（R1 R2……Rn），对应的存储结构为单链表结构
链表插入排序实际上是一个对链表遍历的过程。先将表置为空表，然后依次扫描链表中每个结点，设其指针为p，搜索到p结点在当前子表的适当位置，将其插入。
见day6作业
交换排序：
1、冒泡排序：设记录key集合k={50，36，66，76，95，12，25，36}，排序过程如下：
2、快速排序：设记录的key集合k={50，36，66，76，36，12，25，95}，每次以集合中第一个key为基准的快速排序过程如下：
二、快速排序的实现
代码：
sort.c:
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#include <stdio.h> #include <stdlib.h>//srandom函数需要的头文件 #define N 15 int partion(int *data, int low, int high); int quick_sort(int *data, int low, int high); int compare(const void *p1, const void *p2); int main(int argc, const char *argv[]) { int data[N] = {0}; int i; srandom(10);//设置一个种子才能得到随机值 for (i = 0; i < N; i++) { data[i] = random() % 100;//random返回的值可能比较大，所以对100取余 } for (i = 0; i < N; i++) { printf("%d ", data[i]); } puts(""); //quick_sort(data, 0, N-1);//起点就是下标0，终点是N-1 qsort(data, N, sizeof(int), compare);//qsort函数就是快排（待排数组，元素个数，每一个元素大小，比较函数） for (i = 0; i < N; i++) { printf("%d ", data[i]); } puts(""); return 0; } //第一次排序，找中轴 int partion(int *data, int low, int high) { int temp = data[low];//用temp来存储基准点，第一个基准点默认就是low，最左边的值 while (low < high) {//low和high重合的时候循环结束 while (low < high && temp <= data[high]) {//low<high这个条件是因为如果默认基准点是最小的值，high--，比较到最后high和自己重合了 high--; } data[low] = data[high];//碰到了high位置的值比基准点小，所以把high的值放过来 while (low < high && temp >= data[low]){//上一步放过来之后，现在从左边开始比 low++; } data[high] = data[low]; } data[low] = temp;//找到一个中轴 return low; } int quick_sort(int *data, int low, int high) { int t;//记录中轴的位置 if (data == NULL) { return -1; } if (low >= high)//出口 return 0; t = partion(data, low, high);//找到一个中轴 quick_sort(data, low, t-1);//左半部分继续 quick_sort(data, t+1, high);//右半部分继续，这是一个递归的过程 return 0; } int compare(const void *p1, const void *p2) {//返回值int，两个参数const_void* return (*(const int *)p1 - *(const int *)p2);//先换成int指针 // 第一个元素指待比较第一个元素的地址 }
运行结果：
d13作业：
1、利用快速排序对以下数据进行排序1,5,7,8,3,5,9,4,1,0
代码：2.c
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#include <stdio.h> int a[20],n; void quicksort(int left,int right) { int i,j,t,temp; if(left>right) return; temp=a[left]; //temp用来保存基准数 i=left; j=right; while(i!=j) { //从右边开始找 while(a[j]>=temp && i<j) j--; //再找右边的 while(a[i]<=temp && i<j) i++; //交换两个数在数组中的位置 if(i<j) { t=a[i]; a[i]=a[j]; a[j]=t; } } //将基准数归位 a[left]=a[i]; a[i]=temp; quicksort(left,i-1);//继续处理左边的 quicksort(i+1,right);//处理右边的 } int main() { int i,j,t; scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&a[i]); quicksort(1,n); for(i=1;i<=n;i++) printf("%d ",a[i]); getchar(); getchar(); return 0; }
运行结果：
最后
以上就是炙热电话最近收集整理的关于L3数据结构-排序（day13）一、排序的原理二、快速排序的实现 d13作业：的全部内容，更多相关L3数据结构-排序（day13）一、排序内容请搜索靠谱客的其他文章。
发表评论 取消回复