插入排序–升序
插入排序中有两组数据,一组是有序序列,一组是无序序列,我们需要将无序序列挨个插入到有序序列中
一般我们设置第一个元素为有序序列,后面的元素都是无序序列,无序序列的第一个元素为哨兵与有序序列最后一个值比较
如果哨兵元素比该元素小,就开始排列,先找到要插入的位置(哨兵元素与有序序列元素一一比较)
把该位置之后的所有元素后移,之后将哨兵元素插入到该位置。
对于一个本身有序的序列,直接插入排序的效率比折半插入排序高
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18void insertSort (int arrayA[],int n) { int i,j; int temp;//哨兵 for(i = 1;i < n;i++) { temp = arrayA[i]; //设置哨兵为无序队列第一个 if(temp < arrayA[i-1]) //哨兵值比有序元素值小,开始排列 { for(j = i-1;temp < arrayA[j]&&j >= 0;j--) { arrayA[j+1] = arrayA[j]; //移位将符合条件的元素后移 } arrayA[j+1]= temp; //这里的j+1与上面的j+1不同,这里的j是上面循环结束后的值,表示应该插入的位置 } } }
/*
折半插入排序–升序
在有序序列中用low记录有序序列首位元素下标,用high记录有序序列最后一位元素下标,用mid记录有序序列的中间元素下标
待排序列的首位也就是下标为temp哨兵,当low <= high时,通过比较哨兵的值与有序序列中间mid元素的大小,来确定新的 low 和high 值
如果是temp哨兵值比mid中间值大,说明哨兵值要插入在mid的右边,low=mid+1,反之要插入到mid的左边 high=mid-1;直到low>high结束循环
也就是low和high值确定,之后再对排序序列进行移动,将下标大于high+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
29void BinarySort(int arrayA[],int n) { int i,j,low,high,mid; int temp; for(i = 1;i < n;i++) { temp = arrayA[i]; //哨兵,也就是待插入值 low = 0; high = i-1; while(low <= high) //当low = high时也需要比较,是因为出现有序序列值下标为偶数的情况 { mid = (low + high )/2; if(temp > arrayA[mid]) { low = mid+1; //如果是降序排列这里应该是 high = mid - 1; } else { high = mid - 1; //如果是降序排列这里应该是 low = mid+1; } } for(j = i-1;j >= high+1; j--) //将下标大于high+1的元素全部右移 { arrayA[j+1] = arrayA[j]; } arrayA[high+1] = temp; //这里是 high+1 不是j+1 } }
希尔排序
/*
希尔排序是折半插入排序与直接插入排序的改进,基本思想是按照数组下标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
25void ShellSort(int arrayA[],int n) { int i,j; int temp; int gap; gap = n/2; //分组间距,增量 while(gap > 0) { for(i = gap;i<n;i++)//一轮排序 { temp = arrayA[i]; //哨兵 j = i - gap; //插入比较对象 while(temp < arrayA[j]&&j>= 0) { arrayA[j+gap] = arrayA[j]; j = j - gap; } arrayA[j+gap] = temp; } gap = gap/2;//分组间隙减小,之后重新排序 } }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24void ShellSort_1(int arrayA[],int n) { int i,j; int temp; int gap; gap = n/2; while(gap >0) { for(i = gap;i < n;i++) { temp = arrayA[i]; //哨兵 if(temp < arrayA[i - gap]) //哨兵与要比较值比较 { for(j = i-gap;temp < arrayA[j]&&j >= 0;j = j - gap) { arrayA[j+gap]=arrayA[j]; } arrayA[j+gap] = temp; } } gap = gap/2; } }
/冒泡排序/
冒泡排序基本思想是从第一个元素开始,比较相邻元素的大小,如果比相邻元素大,交换两个元素的位置,经过一轮冒泡最大的元素
将会到序列最后,之后再次进行第二轮冒泡直到所有序列排列完成,可以首先定义一个冒泡标志位,如果在一轮冒泡中出现了数据交换
则表示序列未完成排列,冒泡标志位成立,如果一轮冒泡中没有进行数字交换,则表明序列已经完成排列,冒泡标志位位0,退出循环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25void BubbleSort (int arrayA[],int n) { int i,j; int temp; int flag = 0 ;//进入循环标志位,如果没有进入冒泡排序循环,说明数据已经排列完毕,不需要接下来的冒泡循环,避免了序列已经排好循环还没结束的操作 for(i = 0;i < n-1;i++) //冒泡的轮数 { for(j = 0;j < n-i-1;j++) //每轮冒泡排序过程,也就是每轮数据交换的次数 { if(arrayA[j]>arrayA[j+1]) //数据交换 { temp = arrayA[j]; arrayA[j] = arrayA[j+1]; arrayA[j+1] = temp; flag = 1;//进入循环标志位置1,代表还在继续排列 } } if(flag == 0) { break; } } }
/简单排序/
简单排序与插入排序类似,也是有两组序列,一组是有序序列,一组是待排序列,不同的是简单排序刚开始全都是待排序列
每一次排序先通过循环比较找出待排序列中的最大值下标,交换该最大值元素与待排序列头部元素,直到所有待排序列的数据元素排序完毕
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23void SelectSort(int arrayA[],int n) { int i,j,max; int temp; for(i = 0;i < n;i++) //n次排序交换 { max = i; //定义当前下标最大值 for(j = i;j<n;j++) //查找最大值,并记录下标 { if(arrayA[max] < arrayA[j]) { max = j; } } if(i != max) //找到最大值,并进行交换 { temp = arrayA[max]; arrayA[max] = arrayA[i]; arrayA[i] = temp; } } }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17void mergeArray(int* arrayA, int sizeA, int* arrayB, int sizeB) { int m = 4;//素数下标 int n; for(n = 0;n < sizeB;n++) //数组合并 { arrayA[m] = arrayB[n]; m++; } for(n = 0;n < sizeA;n++) { printf("A[%d]=%dn",n,arrayA[n]); } printf("--------n"); SelectSort(arrayA,sizeA); }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21#define sizeA 15 #define sizeB 11 int main() { int m = 0; int length = 1; //int A[] = {2,4,1,5,3,9,6,8,7,10,0}; int A[sizeA] = {1,3,5,7}; int B[sizeB] = {2,4,6,8,10,11,9,33,22,15,12}; mergeArray(A,sizeA,B,sizeB); // BubbleSort(A,length); for(m =0;m < sizeA;m++) { printf("A[%d]=%dn",m,A[m]); } return 0; }
最后
以上就是雪白花瓣最近收集整理的关于C语言 排序算法集合的全部内容,更多相关C语言内容请搜索靠谱客的其他文章。
发表评论 取消回复