数据结构 15种内部排序方法 --- c语言_c语言数据结构内部排序法

内部排序

排序是计算机内经常进行的一种操作，其目的是将一组"无序"的记录序列调整为"有序"的记录序列。分内部排序和外部排序。若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。

将杂乱无章的数据元素，通过一定的方法按关键字顺序排列的过程叫做排序。假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的;否则称为不稳定的。

排序方法合集
插入：直接插入 折半插入 希尔插入 二路插入
选择：直接选择 二路选择 堆排序 二叉树
交换: 冒泡(起冒) 鸡尾酒 快速排序
归并：二路归并
基数排序
计数排序

直接插入排序

1.简单方法
首先在当前有序区R[1…i-1]中查找R[i]的正确插入位置k(1≤k≤i-1);然后将R[k…i-1]中的记录均后移一个位置，腾出k位置上的空间插入R[i]。
注意:若R[i]的关键字大于等于R[1…i-1]中所有记录的关键字，则R[i]就是插入原位置。

2.改进的方法
一种查找比较操作和记录移动操作交替地进行的方法。具体做法:
将待插入记录R[i]的关键字从右向左依次与有序区中记录Rj的关键字进行比较:
① 若R[j]的关键字大于R[i]的关键字，则将R[j]后移一个位置;
②若R[j]的关键字小于或等于R[i]的关键字，则查找过程结束，j+1即为R[i]的插入位置。
关键字比R[i]的关键字大的记录均已后移，所以j+1的位置已经腾空，只要将R[i]直接插入此位置即可完成一趟直接插入排序。

void insertSort(int arr[],int n){
   
	int i,j;
	//   i=0，只有一个元素  本身就是有序，不需要插入
	//i=1 从第二个元素开始，逐一往前插入  插入之后使之保持有序 
	for(i=1;i<n;i++){
   //i=1  1+2+3+4+...+n-1    n(n-1)/2
		int key = arr[i];//提前保存要插入的元素 因为前面的元素往后移，会覆盖
		//[0,i-1]有序  插入key之后使   [0,i]区间有序
		for(j=i-1;j>=0&&arr[j]>key;--j){
   
			arr[j+1] = arr[j];
		} 
		if(i!=j+1){
   //i==j+1  
			arr[j+1] = key;   //arr[i] = key; 
		}
	} 
}
/*
下标为i的元素要插入到[0,i-1]区间，使插入arr[i]元素
	局部 [0,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

折半插入

方法：

在将一个新元素插入已排好序的数组的过程中，寻找插入点时，将待插入区域的首元素设置为a[low]，末元素设置为a[high]，则轮比较时将待插入元素与a[m]，其中m=(low+high)/2相比较,如果比参考元素小，则选择a[low]到a[m-1]为新的插入区域(即high=m-1)，否则选择a[m+1]到a[high]为新的插入区域(即low=m+1)，如此直至low<=high不成立，即将此位置之后所有元素后移一位，并将新元素插入a[high+1]。

void insertNum(int arr[],int len,int key){
   
	int left,mid,right;
	for(left=0,right=len-2;left<=right;){
   //left>right
		mid = (left+right)/2;
		if(key<arr[mid]){
   
			right = mid-1;
		}else{
   
			left = mid+1;
		}
	} 
	int i;
	for(i=len-2;i>right;--i){
   
		arr[i+1] = arr[i];
	}
	arr[right+1] = key;
	
}
void showArr(int arr[],int len){
   
	int i;
	for(i=0;i<len;i++){
   
		printf("%d ",arr[i]);
	}
	printf("\n");
}
/*
效率最低的情况:
原始数列: 10 9 8 7 6 5 4 3 2 1   升序
	原始序列和最终的序列正好相反的情况，每次插入一个元素
	都需要把该元素插入到最前面，需要把该元素之前所有的元素都往后移一次
*/

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

2-路插入排序

2-路插入排序算法是在折半插入排序的基础上对其进行改进，减少其在排序过程中移动记录的次数从而提高效率。利用一个与排序序列一样大小的数组作为辅助空间，设置left和right指针标记辅助数组开始位置和最后位置。遍历未排序序列，如果待插入元素比已排序序列最小的元素(left位置)小，则left位置前移，将待排序元素插入left位置；如果待插入元素比已排序序列最大的元素(right位置)大，则right位置后移，将待排序元素插入right位置；如果待插入元素比最小大，比最大小，则需要移动元素，过程类似直接插入排序，不过考虑到循环使用数组，对于下标的处理有些许不同。

void twoRoadInsert(int arr[],int n){
   
	int *brr = (int *)malloc(sizeof(arr[0])*n);//brr
	int left = -1,right = n;
	int i,j;
	for(i=0;i<n;i++){
   
		if(left==-1||arr[i]>brr[0]){
   //大于最左端的元素 
			for(j=left;j>=0&&arr[i]<brr[j];--j){
   
				brr[j+1] = brr[j];
			}
			brr[j+1] = arr[i];
			++left;
		}else{
   //小于brr[0] 如果要插入左边 左边所有的元素都要移动 
			for(j=right;j<n&&arr[i]>brr[j];++j){
   
				brr[j-1] = brr[j];
			}
			brr[j-1] = arr[i];
			--right;
		} 
	}
	for(i=right;i<n;i++){
   
		arr[i-right] = brr[i];
	}
	for(i=0;i<=left;i++){
   
		arr[n-right+i] = brr[i];
	}
	free(brr);
}
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

希尔排序