插入排序–升序
插入排序中有两组数据，一组是有序序列，一组是无序序列，我们需要将无序序列挨个插入到有序序列中
一般我们设置第一个元素为有序序列，后面的元素都是无序序列，无序序列的第一个元素为哨兵与有序序列最后一个值比较
如果哨兵元素比该元素小，就开始排列，先找到要插入的位置（哨兵元素与有序序列元素一一比较）
把该位置之后的所有元素后移，之后将哨兵元素插入到该位置。
对于一个本身有序的序列，直接插入排序的效率比折半插入排序高
void 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的元素全部右移，将哨兵插入到移动的元素之前。
*/
void 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，所有序列重新整合成一个序列，排序结束。
*/
void 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;//分组间隙减小，之后重新排序
}
}
void 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，退出循环
void 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;
}
}
}
/简单排序/
简单排序与插入排序类似，也是有两组序列，一组是有序序列，一组是待排序列，不同的是简单排序刚开始全都是待排序列
每一次排序先通过循环比较找出待排序列中的最大值下标，交换该最大值元素与待排序列头部元素，直到所有待排序列的数据元素排序完毕
void 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;
}
}
}
void 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);
}
#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语言内容请搜索靠谱客的其他文章。
发表评论 取消回复