插入排序

即将所需排序的数组分为有序和无序两个部分且有序区在前。每次从无序区中取出一个元素插到有序区的适当位置。

如果需要排序的元素插入有序区的中间，则在插入元素后有序区的每一位元素后移。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*法一：交换元素值*/
void InsertSort(int *p,int n){
	
	int temp;         //用来存储下一个要排序的元素
	int sorted;       //有序区的长度
	int i,j;
	
	for(i = 1 ; i < n ; i++){//从第二个元素开始排序
		sorted = i-1;        //有序区从头到将要排序的元素的前一个
		temp = p[i];         
		while(sorted >= 0 && p[sorted] > temp){     //从后向前比较，将比较和后移工作放在一个while循环里，因为不清楚循环次数所以使用while循环
			p[sorted+1] = p[sorted];                //从要排序的元素开始，前一个元素向后移
			sorted--;
		}
		p[sorted+1] = temp;                         //while循环结束即要排序的元素应在的位置
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*法二：交换元素地址*/
#include <stdio.h>
#include <stdlib.h>
void InsertSort(int *p,int n){
	
	int temp;
	int sorted;
	int i,j;
	int *s = p,*e = p+n-1;
	
	for( ; s < e ; s++){
		sorted = s-p-1;
		temp = *s;
		while(sorted >= 0 && *(p+sorted) > temp){
			*(p+sorted+1) = *(p+sorted);
			sorted--;
		}
		*(p+sorted+1) = temp;
	}
}

归并排序

归并排序是利用递归不断将数组分成两份直到分成每个数组一个元素。然后将分好的有序小数组两两比较进行合并。

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
#include <stdio.h>
#include <stdlib.h>

void merge(int arr[],int temp[],int left,int mid,int right){
	int l_pos = left; //用来存储归并的两个数组中左半部分的首元素
	int r_pos = mid+1;//用来存储归并的两个数组中右半部分的首元素
	int pos = left;//用来存储已经排序好的元素位置
	
	while(l_pos <= mid && r_pos <= right){//当两个数组中有剩余元素时
		if(arr[l_pos] < arr[r_pos]){//将两个有序数组合并
			temp[pos++] = arr[l_pos++];
		}else{
			temp[pos++] = arr[r_pos++];
		}
	}

	while(l_pos <= mid){//如果只有左数组有剩余元素则直接填充
		temp[pos++] = arr[l_pos++];
	}	
	
	while(r_pos <= right){//如果只有右数组有剩余元素则直接填充
		temp[pos++] = arr[r_pos++];
	}	
	
	while(left <= right){//将归并的这一部分复制到元素组中
		arr[left] = temp[left];
		left++; 
	} 
}
void mergeSort(int arr[],int temp[],int left,int right){
	if(left < right){//如果没有划分成只剩一个元素的数组，就继续进行递归划分
		int mid = (left+right) / 2;//设置中间值
		mergeSort(arr,temp,left,mid);//分别划分左半部分
        mergeSort(arr,temp,mid+1,right);//和右半部分
		merge(arr,temp,left,mid,right); //对划分好的数组进行合并
	}
}

void showArr(int arr[],int n){//打印数组
	int i;
	for(i = 0 ; i < n ; i++){
		printf("%d",arr[i]);
	}
	printf("\n");
}
int main(){
 
	int arr[] = {5,7,4,1,6,9,8,2,3};
	int n = 9;
	int *temp = (int*)malloc(sizeof(int));//分配暂时存储的数组
	showArr(arr,n);
	if(temp){
		mergeSort(arr,temp,0,n-1);//如果成功分配则进行排序
	}else{
		printf("ERROR!");
	}
	showArr(arr,n);
	
}

堆排序

堆的定义：若一个数列是堆，则r1必定是数列中的最小值或最大值，并且满足(ri <= r2i && ri <= r2i+1) || (ri >= r2i && ri >= r2i+1)。

如图：1

堆排序即利用堆的特性对记录序列进行排序的一种排序方法。

具体步骤：

  • 先按所需排序的序列建立大顶堆，选出堆顶元素即关键字最大的记录
  • 将关键字最大的记录与序列中最后一个元素交换
  • 重新将前n-1个元素调整为大顶堆
  • 反复过程，直至有序

初始建堆：

我们以序列[40, 55, 73, 12, 98, 27]为例。

由无序序列建成大顶堆的过程是“自下而上”进行筛选的过程。数组有效元素下标从1开始，这样每一个叶结点的两个子节点下标分别为2n和2n+1。