C语言排序算法
随便写写。 人气:0一、冒泡排序
1.原理
从数组的头开始不断比较相邻两个数的大小，不断将较大的数右移，一个循环后，最大数移至最后一位，无序数组规模减一。不断重复前面动作，知道数组完全有序。
2.实现
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void bubble_sort(int* arr, int len)
{
bool issort = false;
while (!issort)
{
issort = true;//如果有序则直接退出
for (int i = 1; i < len; i++)
{
if (arr[i-1] > arr[i])//不断比较相邻两个数
{
swap(&arr[i - 1], &arr[i]);//将较大的数不断往右移
issort = false;//如果进行了交换则无序
}
}
len--;//无序规模减一
}
}3.算法分析
时间复杂度： 最好情况，当数组完全有序，则只需要进行一轮比较，时间复杂度为o(n)；最坏情况为完全无序，每次比较后都要将该数移至数组末尾，时间复杂度为o(n ^2)；平均时间复杂度为o(n ^2)。
空间复杂度： 冒泡排序为就地排序,空间复杂度为o(1)。
稳定排序： 当数字相同时不会改变相对次序。
二、选择排序
1.原理
数组前面为无序，后面为有序。刚开始全是无序，从中选择一个最大值与最后一个无序数字进行交换，无序数组规模减一，有序数组规模加一。不断循环前面操作，直到数组变为有序数组。或者前面为有序数组，后面为无序数组，不断选择最小值与无序数组的第一个数交换，前面的有序数组加一，后面的无序数组减一。
2.实现
void selection_sort(int* arr, int len)
{
int max_index;
while (len)
{
max_index = 0;
for (int i = 1; i < len; i++)
{
if (arr[max_index] < arr[i])
{
max_index = i;//获取最大值的索引
}
}
swap(&arr[max_index], &arr[len - 1]);//将最大值与最后一个值交换
len--;//无序规模减一
}
}3.算法分析
时间复杂度： 所有的复杂度为每次选择最大值，不管数字的有序性，时间复杂度都为o(n)+o(n-1)+…+o(1)=o(n^2)。所以该算法平均复杂度、最好情况、最差情况都为o(n ^2)。
空间复杂度： 就地排序，空间复杂度为o(1)。
不稳定性算法： 排序后相同元素的顺序可能被打乱。例子：选择最大进行排序。3,1,2,2* 第一轮排序后 2*,1,2,3 2的相对顺序发生了改变。选择最小进行排序，2*,2,3,1 第一轮排序后1,2,3,2*. 2的相对顺序也被打乱。如果增加空间复杂度也能将选择排序变成稳定性排序。
三、插入排序
1.原理
数组前面为有序，后面为无序，将无序数组中的第一个数不断插入有序数组中（具体实现为不断比较相邻两数大小，前面一个数大于后一个数，则交换顺序，较小的数不断前移），有序规模增加一，无序规模减小一。或者，数组前面为无序，后面为有序，通过将无序数组的最后一位数字插入有序数组中（具体实现为将无序数组的最后一位与相邻的有序数组不断比较，将无序数组不断右移）。
2.实现
void insert_sort(int arr[], int len)
{
for (int i = 1; i < len; i++)//i前面为有序
{
for (int j = i - 1; j >= 0; j--)//j为有序数的末尾
{
bool issort = true;//当数组有序时能够提前退出
if (arr[j] > arr[j + 1])//将无序数组的第一个数不断与有序数组比较
{
swap(&arr[j], &arr[j + 1]);//将无序数字插入有序数组合适的位置
issort = false;
}
if (issort) break;
}
}
}3.算法分析
时间复杂度： 插入排序和冒泡排序类似，最好情况完全有序则时间复杂度为o(n)，最坏情况为完全无序时间复杂度为o(n^2)，平均复杂度为o(n ^2)。
空间复杂度： 就地排序不需要额外空间，空间复杂度为o(1)。
稳定性排序： 和冒泡排序类似。
四、希尔排序
1.原理
每次选择一个增量进行分组，增量不断减小到一（为插入排序），数组不断变得有序，增量为一时变成完全有序。属于插入排序的改进，通过增量进行分组，对每一组进行插入排序，相比于插入排序的优势在于，shell排序能够大尺度的移动每一组的最小值，而插入排序得挨着进行比较，所以shell排序效率更高。
增量为6：
每一组只有两个数，分别比较两个数的大小，如64,57交换顺序变成57,64，所有的分组比较完后继续缩减增量。
增量为3：
每一组有四个数，总共三组，分别为23,12,53,79；57,9,64,87；24,16,71,97；以增量开始（12开始）遍历数组，遍历到12则在第一组中对12进行插入排序，交换23和12的顺序；遍历到9则在第二组对9进行插入排序。。。。遍历到64对一组中的9,57,64进行插入排序。最后每一组都变得有序。整体有序性变大。
增量为1：
对之前排序过的数组进行插入排序，通过前面的步骤数组有序性变大，最后进行插入排序的效率就更高。
2.实现
void shell_sort(int* arr, int len)
{
int gap = 0; //分组的跨度
int i = 0;
int j = 0;
for (gap = len / 2; gap >= 1; gap /= 2) //分组增量
{
for (i = gap; i < len; i++) { //遍历每组
for (j = i - gap; j >= 0; j -= gap) //对组内进行插入排序
{
if (arr[j] > arr[j + gap])
{
swap(&arr[j], &arr[j + gap]);
}
}
}
}
}3.算法分析
时间复杂度：最好情况为完全有序o(n),最差情况为完全无序o(n^2)，平均复杂度为o(n ^1.3)。
空间复杂度：该算法为就地排序空间复杂度为o(1)。
稳定性：shell排序在分组中可能将相同数字划分成不同的分组，会改变相对顺序，属于不稳定性排序算法。
总结
冒泡排序、选择排序、插入排序、希尔排序的实现都是基于线性表进行实现的（数组或者链表），实现逻辑都是通过比较数字的大小。算法的时间复杂度都比较大，但是属于就地排序，不需要额外空间。几种算法相比之下希尔排序更具有优势。
加载全部内容