排序算法

排序算法（递增）（c语言）

title

title

1.插入排序

算法思想：每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中直到全部记录插入完成

1. 直接插入排序

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。例如要将数组arr=[4,2,8,0,5,1]排序，可以将4看做是一个有序序列，将[2,8,0,5,1]看做一个无序序列。无序序列中2比4小，于是将2插入到4的左边，此时有序序列变成了[2,4]，无序序列变成了[8,0,5,1]。无序序列中8比4大，于是将8插入到4的右边，有序序列变成了[2,4,8],无序序列变成了[0,5,1]。以此类推，最终数组按照从小到大排序。该算法的时间复杂度为O(n^2)。

插入排序算法的原理如下：

​ 1.从第一个元素开始，该元素可以认为已经被排序；

​ 2.取出下一个元素，在已经排序的元素序列中从后向前扫描；

​ 3.如果该元素（已排序）大于新元素，将该元素移到下一位置；

​ 4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；

​ 5.将新元素插入到该位置后；

​ 6.重复步骤2~5。

算法实现:

1
2
3
4
5
6
7
8
9
10
11
12
void InsertSort(int* arr, int len){
	int i, j, temp;
	for (i = 1; i < len; i++) {								//将各元素插入已排好序的序列中
		if (arr[i] < arr[i - 1]) {							//若A[i]关键字小于前驱
			temp = arr[i];					                //用temp暂存A[i]
			for (j = i - 1; j >= 0 && arr[j] > temp; j--)	//检查所有前面已经排好序的元素
				arr[j + 1] = arr[j];						//所有大于temp的元素都向后挪位
			arr[j + 1] = temp;								//复制到插入位置
		}
	}
};

2. 折半插入排序

算法实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void InsertSort_N(int arr[], int len) {
    int i, j, temp, low, high, mid;
    for (i = 1; i < len; ++i) {             //依次将数组中arr[2]~arr[n]插入前面已经排序序列
        temp = arr[i];                      //将arr[i]暂存在temp中
        low = 0;                            //设置折半查找范围
        high = i - 1;
        while (low <= high) {               //折半查找（默认递增有序）
            mid = (low + high) / 2;         //取中间点
            if (arr[mid] > temp)
                high = mid - 1;             //查找右半子表
            else
                low = mid + 1;              //查左半子表
        }
        for (j = i - 1; j >= high + 1; --j)
            arr[j + 1] = arr[j];            //依次后移元素，空出插入位
        arr[high + 1] = temp;               //插入
	}
}

3. 希尔排序

希尔排序：​希尔排序是对插入排序的优化，基本思路是先选定一个整数作为增量，把待排序文件中的所有数据分组，以每个距离的等差数列为一组，对每一组进行排序，然后将增量缩小，继续分组排序，重复上述动作，直到增量缩小为1时，排序完正好有序。

​希尔排序原理是每一对分组进行排序后，整个数据就会更接近有序，当增量缩小为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
void ShellSort(int* arr, int n)
{
	int gap = n;
	while (gap>1)
	{
		//每次对gap折半操作
		gap = gap / 2;
		//单趟排序
		for (int i = 0; i < n - gap; ++i)
		{
			int end = i;
			int tem = arr[end + gap];
			while (end >= 0)
			{
				if (tem < arr[end])
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tem;
		}
	}
}

2.交换排序

1. 冒泡排序

​冒泡排序（Bubble Sort）也是一种简单直观的排序算法。假设长度为n的数组arr，要按照从小到大排序。则冒泡排序的具体过程可以描述为：首先从数组的第一个元素开始到数组最后一个元素为止，对数组中相邻的两个元素进行比较，如果位于数组左端的元素大于数组右端的元素，则交换这两个元素在数组中的位置。这样操作后数组最右端的元素即为该数组中所有元素的最大值。接着对该数组除最右端的n-1个元素进行同样的操作，再接着对剩下的n-2个元素做同样的操作，直到整个数组有序排列。

冒泡排序算法的原理如下：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

算法实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void bubble_Sort(int* a, int n)
{
	int i = 0，j = 0，flag = 0，temp;       //flag表示本趟冒泡是否发生交换的标志
	for (i = 0; i < n - 1; i++)//趟数
	{
		for (j = 0; j < n - 1 - i; j++)    //相邻元素之间的比较次数
		{
			if (a[j + 1] < a[j])           //若为逆序
			{
				temp = a[j+1];	           //交换
				a[j+1] = a[j];
				a[j] = temp;
				flag = 1;
			}
		}
		if (flag == 0)
		{
			break;			              //本趟遍历后没有发生交换，说明表已经有序
		}
	}
}

2. 快速排序

基本思想为:
任取待排序元素中的某元素作为基准值pivot，按照该基准值将带排序序列分为两个子序列，左边子序列的值都小于基准值，右边则都大于基准值，然后左右序列重复该过程（递归），直到所有元素都排列在相遇的位置上为止。

算法实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//用第一个元素将待排序序列划分成左右两个部分
int Partition(int A[],int low,int high){
	int pivot = A[low];
	while(low<high){
		while(low<high&&A[high]>=pivot){
		high--;
		}
		A[low] = A[high];
		while(low<high&&A[low]<=pivot){
		low++;
		}
		A[high] = A[low];
	}
	A[low] = pivot;
	return low;
}
//快速排序
void QuickSort(int A[],int low,int high){
	if(low<high){     //递归跳出的条件
		int pivotpos = Partition(A,low,high); //划分
		QuickSort(A,low,pivotpos-1);
		QuickSort(A,pivotpos+1,high);
	}
}

选择排序

1. 简单选择排序

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。具体来说，假设长度为n的数组arr，要按照从小到大排序，那么先从n个数字中找到最小值min1，如果最小值min1的位置不在数组的最左端(也就是min1不等于arr[0])，则将最小值min1和arr[0]交换，接着在剩下的n-1个数字中找到最小值min2，如果最小值min2不等于arr[1]，则交换这两个数字，依次类推，直到数组arr有序排列。算法的时间复杂度为O(n^2)。

选择排序算法的原理如下：

​ 1.首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

​ 2.再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

​ 3.重复第二步，直到所有元素均排序完毕。

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
// 自定义方法：交换两个变量的值
void swap(int *a,int *b) 
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
/* 选择排序 */
void selection_sort(int arr[], int len)
{
    int i,j;
    for (i = 0 ; i < len - 1 ; i++) {
        int min = i;
        for (j = i + 1; j < len; j++) {    //  遍历未排序的元素
            if (arr[j] < arr[min]) {  	   //  找到目前最小值下标j
                min = j;   				   //  记录最小值小标
            }
        }
        swap(&arr[min], &arr[i]);    	   //做交换
        /*  
			不用自定义函数时可以用选择下面方式进行交换
			temp = arr[min];
        	arr[min] = arr[i];
        	arr[i] = temp;
		*/

    }
}

2. 堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：每个结点的值都大于等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于等于其左右孩子结点的值，称为小顶堆。该算法时间复杂度为O(n log n)。

堆排序算法的原理如下：

​ 1.将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；

​ 2.将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；

​ 3.由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-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
void swap(int* a, int* b){					//交换函数
	int temp;
	temp = *b;
	*b = *a;
	*a = temp;
};

// 下标为i的节点的父节点下标:(i-1)/2
// 下标为i的节点的左孩子下标:i*2+1
// 下标为i的节点的右孩子下标:i*2+2
void Heapify(int arr[], int n, int i) {  //维护堆的性质 arr:存储堆的数组 n:数组长度 i:待维护节点的下标
	int largest = i;
	int lson = i * 2 + 1;
	int rson = i * 2 + 2;
	
	if (lson < n && arr[largest] < arr[lson]) //子节点下标不能超出n，如果存在子节点大于父节点，就把最大子节点下标赋给largest
		largest = lson;
	if (rson < n && arr[largest] < arr[rson])
		largest = rson;
	if (largest != i) {
		swap(&arr[largest], &arr[i]);		 //交换子节点和父节点
		Heapify(arr, n, largest);			 //递归维护子节点
	}	

}

void Heapsort(int arr[], int n) {
	int i;
	//建堆
	for (i = ((n - 1) - 1) / 2; i >= 0; i--) {
		Heapify(arr, n, i);
	}
	for (i = n - 1; i > 0; i--) {
		swap(&arr[i], &arr[0]);				//将排好序的放到数组最后面
		Heapify(arr, i, 0);					//维护堆顶
	}
};

归并排序

​归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。代价是需要额外的内存空间。若将两个有序表合并成一个有序表，称为2-路归并。 该算法时间复杂度为O(n log n)。

希尔排序算法的原理如下：

​1.把长度为n的输入序列分成两个长度为n/2的子序列；

​2.对这两个子序列分别采用归并排序；

​3.将两个排序好的子序列合并成一个最终的排序序列。

代码实现如下:

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
// 合并
void merge(int arr[], int temparr[], 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])		//左半区第一个剩余元素更小
			temparr[pos++] = arr[l_pos++];
		else								//右半区第一个剩余元素更小
			temparr[pos++] = arr[r_pos++];
	}
	// 合并左半区剩余的元素
	while (l_pos <= mid)
		temparr[pos++] = arr[l_pos++];
	while (r_pos <= right)
		temparr[pos++] = arr[r_pos++];

	//把临时数组中合并后的元素复制回原来的数组
	while (left <= right) {
		arr[left] = temparr[left];
		left++;
	}
}
// 归并排序
void msort(int arr[], int temparr[], int left, int right) {
	//如果只有一个元素，那么就不需要划分
	//只有一个元素的区域，本身就是有序的，只需要被归并即可
	if (left < right) {
		//找中间点
		int mid = (left + right) / 2;
		//递归划分左半区
		msort(arr, temparr, left, mid);
		//递归划分右半区
		msort(arr, temparr, mid + 1, right);
		//合并已经排好序的部分
		merge(arr, temparr, left, mid, right);
	}
}

//归并排序入口
void mergesort(int arr[], int n) {
	//分配一个辅助数组
	int* temparr = (int*)malloc(n * sizeof(int));
	if (temparr != NULL)			//数组分配成功
	{
		msort(arr, temparr, 0, n - 1);
		free(temparr);
	}
	else {
		printf("malloc fault!");
	}
}

计数排序

​ 计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。计数排序不是基于比较的排序算法。而是 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 Θ(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。该算法时间复杂度为O(n+k)。

代码如下：

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
void Countsort(int* arr, int n)
{
	//找到序列中的最大值和最小值
	int max = arr[0];
	int min = arr[0];
	for (int i = 0; i < n; i++)
	{
		if (arr[i] > max)
		{
			max = arr[i];
		}
		if (arr[i] < min)
		{
			min = arr[i];
		}
	}

	int range = max - min + 1;//开辟空间的数量
	int* countArr = (int*)malloc(sizeof(int) * range);//开辟空间
	//初始化数组全部为0
	memset(countArr, 0, sizeof(int) * range);
	//开始计数
	for (int i = 0; i < n; i++)
	{
		countArr[arr[i] - min]++;
	}

	//开始排序
	int j = 0;
	for (int i = 0; i < range; i++)
	{
		while (countArr[i]--)
		{
			arr[j] = i + min;
			j++;
		}
	}
	free(countArr);
}

桶排序

桶排序（Bucket sort）或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后依次把各个桶中的记录列出来记得到有序序列。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ(n)）。但桶排序并不是比较排序，他不受到O(n log n)下限的影响。

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
//整体思想大致为用数组单元内存放的为结构体式的链表，每个链表称为一个桶。通里面容纳的都是键值相同的元素。 
//之后便是查看对应元素的键值，然后放进与之对应的桶，还需注意桶为空和不空的时的放入方式
//桶元素的插入就是看桶以什么方式的实现。这里桶以链表的形式表现，所以桶中元素的插入即为链表中数组的插入。
/*只要桶的数量够多，那么之前的放入操作只需花费O（n)的时间，而后面的对每个桶里面的元素进行排序则需要基于比较的排序算法。因此后面算法的选择也是
  关乎桶排序速度的重要因素。
 */
 //桶排序的特点是要有界限分明的桶，而不能是无限个桶，也就是说桶排序的个数应该是可以确定的，有限个的。 
 //这里链表实现桶排序的还有要注意的点，就是数组的首地址其实链表的头节点，有这里的值确定该桶的元素个数，并由这里出发寻找其他元素。 
typedef struct node* Snode;
typedef struct node {
	int key;
	Snode next;
}BBc;

void BucketSort(int keys[], int keys_size, int bucket_size)
{
	Snode* bucket_table = (Snode*)malloc(bucket_size * sizeof(Snode));//为结构体数组分配空间。 
	for (int i = 0; i < bucket_size; i++)//对每个数组单元赋予内存空间时，初始化每个结构体数组单元。 
	{
		bucket_table[i] = (Snode)malloc(sizeof(Snode));//这一步是必要的，因为之前只是给数组分配了一连串的存储空间，但是每个单元的存储地址都是 
		//不确定，也不确定该方式是否会自动地分配内存空间给每个数组单元。 
		//那么这样准确的给数组单眼分配的空间是占用之前的分配给数组的空间，还是重新分拨其他的空间给数组单元。
		//其实应该是分配之前给整个数组单元分配的一段存储空间。 
		bucket_table[i]->key = 0;
		bucket_table[i]->next = NULL;
	}//其实创建数组这部分应该放在主函数那里，否则某些功能只能在这个函数中使用。 
	for (int j = 0; j < keys_size; j++)
	{
		Snode node_branch = (Snode)malloc(sizeof(Snode));//定义一个节点，满足条件时链入以链表为表现形式的桶。 
		node_branch->key = keys[j];
		node_branch->next = NULL;
		int index = keys[j] / 10;
		Snode p = bucket_table[index];//p用来充当指向循环的变量。 
		//桶为空和非空时的两种插入形式 
		if (p->key == 0) {
			bucket_table[index]->next = node_branch;
			(bucket_table[index]->key)++;
		}
		//链表的插入形式，按照大小从后到大。 
		else {
			while (p->next != NULL && p->next->key <= node_branch->key) {
				p = p->next;
			}
			node_branch->next = p->next;
			p->next = node_branch;
			(bucket_table[j]->key)++;
		}
	}
	//以此输出每个桶中的所有元素。 
	for (int i = 0; i < bucket_size; i++) {
		for (Snode k = bucket_table[i]->next; k != NULL; k = k->next) {
			printf(" %d ", k->key);
		}
	}

}

基数排序

​基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。该算法时间复杂度为O(n+k)。

基数排序算法的原理如下：

​ 1.取得数组中的最大数，并取得位数；

​ 2.arr为原始数组，从最低位开始取每个位组成radix数组；

​ 3.对radix进行计数排序（利用计数排序适用于小范围数的特点）。

代码如下：

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
/* 基数排序
 * 1.求出数组中最大的元素
 * 2.求出最大元素是几位数, 设为i位
 * 3.对所有的数进行i轮排序. 
 *   首先排个位, 然后是十位, 然后百位
 * 4.每一轮的排位都需要分桶, 桶是有顺序的,
 *   然后把桶里的数按顺序放入原来的数组中.
 * 5.直到i轮排序结束后, 数组排序完成.      */

/*获取数字的位数*/
int figure(int num)
{
    int count = 1;
    int temp = num / 10;

    while(temp != 0)
    {
        count++;
        temp /= 10;
    }

    return count;
}

/*查询数组中的最大数*/
int max(int *a, int n)
{
    int max = a[0];
    int i;

    for(i=1; i<n; i++)
    {
        if(a[i] > max)
        {
            max = a[i];
        }
    }

    return max;
}

/*将数字分配到各自的桶中, 然后按照桶的顺序输出排序结果*/
void sort2(int *a, int n, int loop)
{
    int *buckets[10] = {NULL};
    int c[10] = {0};
    int d[10] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};
    int i, j, k;
    int row;
    int temp = d[loop-1];

    /*统计每个桶的元素个数*/
    for(i=0; i<n; i++)
    {
        row = (a[i] / temp) % 10;

        c[row]++;
    }

    /*为每个桶分配空间*/
    for(i=0; i<10; i++)
    {
        buckets[i] = (int *)malloc(c[i]*sizeof(int));
    }

    memset(c, 0x00, sizeof(c));

    /*将数组中的数据分配到桶中*/
    for(i=0; i<n; i++)
    {
        row = (a[i] / temp) % 10;

        buckets[row][c[row]] = a[i];

        c[row]++;
    }

    k = 0;

    /*将桶中的数, 倒回到原有数组中*/
    for(i=0; i<10; i++)
    {
        for(j=0; j<c[i]; j++)
        {
            a[k] = buckets[i][j];
            k++;
        }
    }

    /*释放桶内存*/
    for(i=0; i<10; i++)
    {
        free(buckets[i]);
        buckets[i] = NULL;
    }
}

/*基数排序*/
void sort3(int *a, int n)
{
    int m = max(a, n);
    int loop = figure(m);
    int i;

    for(i=1; i<=loop; i++)
    {
        sort2(a, n, i);
    }
}

Title:排序算法

Author:

Created:2023-06-10, 19:21:31

Updated:2023-06-10, 19:21:31

Full URL:https://isyang666.github.io/2023/06/10/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/

License: "CC BY-NC-SA 4.0" Keep Link & Author if Distribute.

Contents
  1. 1. 排序算法（递增）（c语言）
    1. 1.1. 1.插入排序
      1. 1.1.1. 1. 直接插入排序
      2. 1.1.2. 2. 折半插入排序
      3. 1.1.3. 3. 希尔排序
    2. 1.2. 2.交换排序
      1. 1.2.1. 1. 冒泡排序
      2. 1.2.2. 2. 快速排序
    3. 1.3. 选择排序
      1. 1.3.1. 1. 简单选择排序
      2. 1.3.2. 2. 堆排序
    4. 1.4. 归并排序
    5. 1.5. 计数排序
    6. 1.6. 桶排序
    7. 1.7. 基数排序
|