数据结构（C语言）-排序_c语言简单排序概念是什么

一、排序的基本概念

为了查找方便，通常希望查找表是按关键字有序排序的，因此学习和研究各种排序的方法和对应的算法，有助于提高计算机对数据处理的工作效率。首先了解一些和排序相关的概念。
1.排序( Sorting )
将数越元素(或记录)的任意序列，重新排列成 个按关健字有序(递增或递减)的序列的过程称为排序。
2.排序过程中的两种基本操作
(1)比较两个关键字值的大小。
(2)根据比较结果，移动记录的位置。
3.对关键字排序的三个原则
(1)关键字值为数值型的，则按键值大小为依据。
(2)关键字值为ASCII码，则按键值的内码编排顺序为依据。
(3)关键字值为汉字字符串类型，则大多以汉字拼音的字典次序为依据。
4.待排序记录的三种存储方式
(1)待排序记录存放在地址连续的一组存储单元上。
(2)待排序记录存放在静态链表中。
(3)待排序记录存放在一组地址连续的存储单元， 同时另设个指示各 个记录存储位置的地址向量，在排序过程中不移动记录本身，而移动地址向量中这些记录的“地址”，在排序结束后，再按照地址向量中的值调整记录的存储位置。
5.内部排序
整个排序过程完全在内存中进行，称为内部排序。
6.外部排序
由于待排序记录数据量太大，内存无法容纳全部数据，排序需要借助外部存储设备才能完成，称为外部排序。
7.稳定排序和不稳定排序
假设Ki=Kj(1≤i≤n, 1≤j≤n, i不等于j),若在排序前的序列中R;领先于R;(即ikj),经过排序后得到的序列中Ri仍领先于Rj则称所用的排序方法是稳定的;反之，若相同关键字的先后次序在排序过程中发生变化，则称所用的排序方法是不稳定的。
定待排序的记录均是以顺序存储结构存放的，且假定记录的关键字均为整数。另外，假定待排序的记录均是以顺序存储结构存放的，且假定记录的关键字均为整数。另外，假定要排序的记录是按递增顺序进行排序。
排序记录的数据类型定义如下:

#include<stdio.h>
#include<stdlib.h>
#define MAX 100 //宏定义 
typedef struct {//构造线性表 
	int data[MAX];
	int length; 
}sort;
1
2
3
4
5
6
7

二、插入排序

■ 基本操作:有序插入
■ 在有序序列中插入一个元素，保持序列有序，有序长度不断增加。
■ 起初，a[0]是长度为1的子序列。然后，逐一将a[1]至a[n-1]插入到有序子序列中。

1、有序插入方法

■ 在插入a[i]前，数组a的前半段(a[0]~a[i-1])是有序段，
后半段(a[i]~a[n-1])是停留于输入次序的"无序段”。
■ 插入a[i]使a[0]~a[i-1]有序，也就是要为a[i]找到有序位置j (0≤j≤i) ,
将a[i]插入在a[j]的位置上。

2、直接插入排序

■ 直接插入排序——采用顺序查找法查找插入位置

1、复制插入元素 x=a[i];
2、记录后移，查找插入位置 for(j=i-1;j> =0&&x<a[j];j--)a[j+1]=a[j];
3、插入到正确位置 a[j-1]=x;
■ 算法分析

void DirectSort(sort *L){//直接插入排序法 
    printf("--直接插入排序--\n");
	int i,j;
	for(i=2;i<=L->length;i++){ 
		L->data[0]=L->data[i];//设置哨兵 
		j=i-1;
		while(L->data[0]<L->data[j]){
			L->data[j+1]=L->data[j];
			j=j-1;
		}
		L->data[j+1]=L->data[0];
	}
	printf("直接插入排序后的线性表：");
	for(i=1;i<L->length;i++){
		printf("%5d",L->data[i]);
		
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

■ 效率分析
从空间角度来看，它只需要一个辅助空间r[0]。
从时间耗费角度来看，主要时间耗费在关键字比较和移动元素上。
向有序表中逐个插入记录的操作，进行了n-1 趟，每趟操作分为比较关键字和移动记录，而比较的次数和移动记录的次数取决于待排序列按关键字的初始排列。
最好情况下:即待排序列已按关键字有序，每趟操作只需1次比较2次移动(仅有的两次移动是将待插入的记录移动到监视哨，再从监视哨移出)，算法的比较次数和移动次数分别为:
总比较次数=n-1；总移动次数=2 (n-1)
最坏情况下:如果待排序列是逆序的，将r(心]插入到适合位置，要进行i-1 次关键字的比较，记录移动次数为i- 1+2。算法的比较次数和移动次数达到最大值，分别为:
总比较次数=总移动次数=
因此，直接插入排序的时间复杂度为O(n2)。该算法只使用了存放监视哨的1个附加空间，它的空间复杂度为O(1)。

2、折半插入排序

■ 折半插入排序大至与折半查找一样

void Halfsort(sort *L){//折半排序 
    printf("\n--折半排序--\n");
    Initialization(L);
     Establish(L);
     int i,j,low,high,mid;
	 for(i=2;i<L->length;++i){
	 	L->data[0]=L->data[i];//设置哨兵 
	 	low=1;high=i-1;
	 	while(low<=high){
	 		mid=(low+high)/2;
	 		if(L->data[0]<L->data[mid]){
	 			high=mid-1;
			 }else{
			 	low=mid+1;
			 }
		 }
		 for(j=i-1;j>=high+1;--j){
		 L->data[j+1]=L->data[j];
     	}
		L->data[high+1]=L->data[0];	 
	 }
	 printf("折半排序后的线性表：");
	for(i=1;i<L->length;i++){
		printf("%5d",L->data[i]);
		
	}
} 
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

■ 折半插入排序–算法分析
折半查找比顺序查找快，所以折半插入排序就平均性能来说比直按插入排序要快;
它所需要的关键码比较次数与待排序对象序列的初始排列无关，仅依赖于对象个数。在插入第i个对象时，需要经过Llog2iJ + 1次关键码比较，才能确定它应插入的位置;
当n较大时，总关键码比较次数比直接插入排序的最坏情况要好得多，但比其最好情况要差;
在对象的初始排列已经按关键码排好序或接近有序时，直接插入排序比折半插入排序执行的关键码比较次数要少;

3、希尔排序( Shell’s Sort )

希尔排序又称为缩小增量排序，它也是种插入排序方法， 但在时间上比直接插入排序方法有较大的改进。

（1）希尔排序的基本思想
先将待排序的记录划分为若干子序列分别进行直接插入排序，当记录的排列已经基本有序，最后再对所有的记录进行一次直接插入排序 。希尔排序的具体方法如下:

• 取定一个正整数d1<n, 把d1作为间隔值，把全部记录从第-个记录起进行 分组，所有距离为 di倍数的记录放在一组中，在各组内进行直接插入排序。
• 取定一个正整数d2<d1,重复上述分组和排序工作，直至取d=1为止，即所有记录在一个组中进行直接插入排序。
  （2）希尔排序算法

void ShellSort(sort *L){//希尔排序 
	printf("\n--希尔排序--\n");
	 Initialization(L);
     Establish(L);
     int i,j,b;
     b=L->length/2;
     while(b>0){
     	for(i=b;i<=L->length;i++){
     		L->data[0]=L->data[i];//设置哨兵 
     		j=i-b;
     		while(j>=0&&L->data[0]<L->data[j]){
     			L->data[j+b]=L->data[j];
     			j=j-b;
			 }
			 L->data[j+b]=L->data[0];
			 j=j-b;
		 }
		 b=b/2;
	 }
	printf("希尔排序后的线性表：");
	for(i=1;i<L->length;i++){
		printf("%5d",L->data[i]);
		
	}
}
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

（3）希尔排序算法分析
希尔排序算法效率与增量序列的取值有关

• Hibbard增量序列
  ■ Dk=2^(k-1)——相邻元素互质
  ■ 最坏情况: Tworst=O(n^(3/2))
  ■ 猜想: Tavg=O(n^(5/4))
• Sedgewick增量序列
  ■ {1,5,19,41,19…}
  ■ 9*4^i-9*2i+ 1或4^i-3*2i+1
  ■ 猜想:Tavg=O(n^(7/6) )Tworst=O(n^(4/3))
  希尔排序的分析是个复杂的问题， 因为它的时间是所取“增量“序列的函数，这涉及一些数学上尚未解决的难题。有人在大量实验的基础上推出:当n在某个特定范围内希尔排序所需的比较和移动次数约O(n^{1.3),所以其平均时间复杂度是O(n}1.3).其辅助空间为O(1),希尔排序是一个不稳定排序。

  三、交换排序

  交换排序的基本方法是:通过两两比较待排序记录的关键字，若有不满足次序要求的一对数据则交换， 直到全部满足为止。本节主要介绍冒泡排序和快速排序这两种排序方法。

  1、冒泡排序 ( Bubble Sort )

  （1）.冒泡排序的基本思想
  冒泡排序是交换排序中种简单的排序方法。 它的基本思想是对所有相邻记录的关键字值进行比较，如果是逆序(r[j]>[j+1]), 则将其交换，最终达到有序化。其处理过程为:
  • 将整个待排序的记录序列划分成有序区和无序区。初始状态有序区为空，无序区包括所有待排序的记录
  • 对无序区从前向后依次将相邻记录的关键字进行比较，若逆序则将其交换，从而使得关键字值小的记录向上“飘”(左移)，关键字值大的记录向下“沉”(右移)。
    每经过-趟冒泡排序，都使无序区中关键字值最大的记录进入有序区，对于由n个记录组成的记录序列，最多经过n-1趟冒泡排序，就可以将这n个记录重新按关键字顺序排
    优点:每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素;
    例1：如何提高效率?
    答：一旦某-趟比较时不出现记录交换，说明已排好序了，就可以结束本算法。
    （2）冒泡排序算法

void BubbleSort(Exchange *l){
	Initialize(l);
	Assignment(l);
	printf("--冒泡排序--\n");
	int i,j,team,flat=1;
	for(i=1;i<=l->length&&flat==1;i++){
		flat=0;
		for(j=0;j<l->length-i;j++){
			if(l->data[j]>l->data[j+1]){
				team=l->data[j];
			    l->data[j]=l->data[j+1];
				l->data[j+1]=team;
				flat=1;
			}
		}
	}
	printf("冒泡排序后的线性表：");
	for(i=0;i<l->length;i++){
		printf("%5d",l->data[i]);
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

（3）冒泡排序算法分析
空间效率：O(1)

■ 冒泡排序最好时间复杂度是O(n)
■ 冒泡排序最坏时间复杂度为O(n2)
■ 冒泡排序平均时间复杂度为O(n2)
■ 冒泡排序算法中增加一个辅助空间temp,辅助空间为S(n)=O(1)
■ 冒泡排序是稳定的

2、快速排序

■ 基本思想:通过一趟排序，将待排序记录分割成独立的两部分，其， 部分记录的关键字均比另一部分记录的关键字小， 则可分别对这两部分记录进行排序，以达到整个序列有序
■ 具体实现:选定一个中间数作为参考，所有元素与之比较，小的调到其左边，大的调到其右边。
(枢轴)中间数:可以是第一 个数、最后一个数、最中间一个数、任选一个数等。

■ 算法

void QuickSort(Exchange *l,int first,int end){
	int team;
	int i,j,k;
	i=first;j=end;team=i;
	while(i<j){
		while(i<j&&l->data[i]>=l->data[j]&&i!=0){
			k=l->data[i];
			l->data[i]=l->data[j];
   			l->data[j]=k;
			j--;
			break; 
	    }
		if(i==((l->length+1)/2)-1){
		   j--;
		}
		while(i<j&&l->data[i]>=l->data[j]){
			k=l->data[j];
			l->data[j]=l->data[i];
			l->data[i]=k;
			break;
		}
		i++;
      }
		if(first<i-1){
			QuickSort(l,first,i-1);
		}
		if(i+1<end){
			QuickSort(l,i+1,end);
		}
}
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

①每一趟的子表的形成是采用从两头向中间交替式逼近法;
②由于每趟中对各子表的操作都相似，可采用递归算法。
■ 快速排序算法分析

• 空间复杂度
  快速排序不是原地排序
  由于程序中使用了递归，需要递归调用栈的支持,而栈的长度取决于递归调用的深度。(即使不用递归， 也需要用用户栈)
• 在平均情况下:需要O(logn)的栈空间
• 最坏情况下:栈空间可达O(n)。
  例2：试对( 90, 85, 79, 74, 68, 50, 46 )进行快速排序的划分
  ■你是否发现什么特殊情况?
  ■再对(46, 50, 68, 74 ，79, 85，90 )进行快速排序划分呢?
  解：由于每次枢轴记录的关键字都是大于其它所有记录的关键字，致使一次划分之 后得到的好序列(1)的长度为0，这时已经退化成为没有改进措施的冒泡排序。
• 快速排序不适于对原本有序或基本有序的记录序列进行排序。
• 划分元素的选取是影响时间性能的关键
• 输入数据次序越乱，所选划分元素值的随机性越好，排序速度越快，快速排序不是自然排序方法。
• 改变划分元素的选取方法，至多只能改变算法平均情况的下的世界性能，无法改变最坏情况下的时间性能。即最坏情况下，快速排序的时间复杂性总是O(n^2)。

四、选择排序

1、简单选择排序

（1）基本思想:在待排序的数据中选出最大(小) 的元素放在其最终的位置。
（2）基本操作:
■首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一一个记录交换
■再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换
■重复上述操作，共进行n-1趟排序后，排序结束
（3）算法

void SelectSort(choice *l){
	printf("--直接选择排序--\n");
	Establish(l);
	int i,j,k,x;
	for(i=1;i<=l->length;i++){
		k=i;
		for(j=i+1;j<=l->length;++j){
			if(l->data[j]<l->data[k]){
				k=j;
		   }
		}
		if(k!=i){
			x=l->data[i];
			l->data[i]=l->data[k];
			l->data[k]=x;
		}
	}
	printf("直接排序后的结果："); 
	for(i=1;i<l->length;i++){
		printf("%5d",l->data[i]);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

（4）简单选择排序算法分析
时间复杂度

• 记录移动次数
  最好情况: 0
  最坏情况: 3(n-1)
• 比较次数:无论待排序列处于什么状态，选择排序所需进行的"比较"次数都相同
  
  算法稳定性
• 简单选择排序是不稳定排序

2、堆排序

若在输出堆顶的最小值(最大值)后，使得剩余n-1个元素的序列重又建成-个堆，则得到n个元素的次小值(次大值) …如此反复，便能得到一个有序序列，这个过程称之为堆排序。
（1）堆的定义:
若n个元素的序列{a1 a2 … an}满足

则分别称该序列{a1 a2 … an}为小根堆和大根堆。从堆的定义可以看出，堆实质是满足如下性质的完全二叉树:二叉树中任一非叶子结点均小于(大于)它的孩子结点
（2）堆的调整
例3：如何在输出堆顶元素后，调整剩余元素为一个新的堆?
小根堆:
1.输出堆顶元素之后，以堆中最后一个元素替代之;
2.然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换;
3.重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为"筛选"
（3）筛选算法

void HeapAdjust(choice *l,int s,int m){
	int j;
	int tmp=l->data[s];
	for(j=2*s;j<=m;j*=2){
		if(j<m&&l->data[j]<l->data[j+1]){
			++j;
		}
		if(tmp>=l->data[j]){
			break;
		}
		l->data[s]=l->data[j];
		s=j;
	}
	l->data[s]=tmp;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

（4）建堆算法

void HeapSort(choice *l){
	printf("\n--堆排序--\n");
	Establish(l);
	int i,tmp,n;
	n=l->length;
	for(i=n/2;i>=1;i--){
		HeapAdjust(l,i,n);
	}
	for(i=n;i>=1;i--){
		tmp=l->data[1];
		l->data[1]=l->data[i];
		l->data[i]=tmp; 
		HeapAdjust(l,1,i-1);
	}
	printf("堆排序后的结果："); 
	for(i=1;i<l->length;i++){
		printf("%5d",l->data[i]);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

（5）算法性能分析

• 堆排序的时间主要耗费在建初始堆和调整建新堆时进行的反复筛选上。堆排序在最坏情况下，其时间复杂度也为O(nlog2n)，这是堆排序的最大优点。无论待排序列中的记录是正序还是逆序排列，都不会使堆
  排序处于最好"或"最坏”的状态。
• 另外，堆排序仅需一个记录大小供交换用的辅助存储空间。
• 然而堆排序是一-种不稳定的排序方法，它不适用于待排序记录个数n较少的情况，但对于n较大的文件还是很有效的。

五、各种排序算法比较