摘要：八大排序的C和Python实现，缓慢更新中...学到哪更新到哪（脑袋瓜笨啊~）
冒泡排序
冒泡排序作为C语言for循环讲解的启蒙例子，相信大家对他都很熟悉
主要思路：
- 比较相邻的元素，根据规则选择是否交换这两个数
- 从开始第一对到结尾最后一对
- 针对多个元素重复以上操作（除了最后一个）
- 时间复杂度：平均O(n^2) 最好：O(n)
- 空间复杂度：O(1)
- 稳定性：稳定
C：
void bubble_sort(int *arr,int len)
{
int i,j,tmp;
int swap = 1;
for(i = 0; i< len-1;i++)
{
for(j = 0; j< len -1 -i; j++)
if(arr[j] > arr[j+1])
{
tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
swap = 0;
}
if(swap) //如果没进行交换直接退出
return;
}
}
Python:
def bubble_sort(arr:[int])-> [int]:
swap = True
for i in range(0,len(arr)-1):
for j in range(0,len(arr)-1-i):
if arr[j] > arr[j+1]:
arr[j],arr[j+1] = arr[j+1],arr[j]
swap = False
if swap:
return arr
return arr
简单选择排序
主要思路：每趟从待排序的记录中选出关键字最小的记录，顺序放在已排序的记录序列末尾，直到全部排序结束为止。
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
- 稳定性：不稳定
C:
void select_sort(int *arr,int len)
{
int i,j,tmp;
int min;
for(i = 0;i<len;i++)
{
min = i;
for(j=i + 1;j<len;j++)
if(arr[j] < arr[min])
min = j;
tmp = arr[i];
arr[i]=arr[min];
arr[min] = tmp;
}
}
Python:
def select_sort(arr:[int])-> [int]:
for i in range(0,len(arr)):
min_index = i
for j in range(i+1,len(arr)):
if arr[min_index] > arr[j]:
min_index = j
arr[min_index],arr[i] = arr[i],arr[min_index]
return arr
插入排序
主要思路：每一趟将一个待排序的记录，按照其关键字的大小插入到有序队列的合适位置里，直到全部插入完成。
- 时间复杂度：平均:O(n^2) 最好:O(n)
- 空间复杂度：O(1)
- 稳定性：稳定
C:
void insert_sort(int *arr,int len)
{
int i,j;
int tmp = 0;
for(i = 1;i< len;i++)
{
tmp = arr[i];
for(j = i-1;j>=0;j--)
if(arr[j] > tmp)
arr[j+1] = arr[j];
else
break;
arr[j+1] = tmp;
}
}
Python:
def insert_sort(arr:[int])-> [int]:
for i in range(1,len(arr)):
tmp = arr[i]
j = i - 1
while j>=0 and arr[j] > tmp:
arr[j+1] = arr[j]
j = j - 1
arr[j+1] = tmp
return arr
希尔排序
希尔(Shell)排序又称为缩小增量排序，它是一种插入排序。它是直接插入排序算法的一种改进版。希尔排序的比较次数和移动次数都要比直接插入排序少，当N越大时，效果越明显。
算法思想：
我们举个例子来描述算法流程（以下摘自维基百科）：
假设有这样一组数 {13, 14, 94, 33, 82, 25, 59, 94, 65, 23, 45, 27, 73, 25, 39, 10}，如果我们以步长为 5 开始进行排序：
| 排序前 | 排序后 |
|---|---|
| 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 | 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 |
将上述四行数字，依序接在一起时我们得到：{10, 14, 73, 25, 23, 13, 27, 94, 33, 39, 25, 59, 94, 65, 82, 45}，然后再以 3 为步长：
| 排序前 | 排序后 |
|---|---|
| 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 | 10 14 13 25 23 33 27 25 59 39 65 73 45 94 82 94 |
最后以 1 为步长进行排序（此时就是简单的插入排序了）。
可想而知，步长的选择是希尔排序的重要部分。算法最开始以一定的步长进行排序，然后会继续以更小的步长进行排序，最终算法以步长为 1 进行排序。当步长为 1 时，算法变为直接插入排序，这就保证了数据一定会被全部排序。
- 时间复杂度：平均:O(nlogn) 最坏:O(n^2)
- 空间复杂度：O(1)
- 稳定性：不稳定
C:
void shell_sort(int *arr,int len,int gap)
{
int tmp;
int i,j;
for(i = gap; i<len; i = i+gap)
{
tmp = arr[i];
for(j = i -gap;j>=0;j=j-gap)
if(arr[j] > tmp)
arr[j+gap] = arr[j];
else
break;
arr[j+gap] = tmp;
}
}
void Shell(int *arr,int len)
{
int gap[] = {5,3,1}; //可以分为步长的一半，这里就自定义好了
int len_gap = sizeof(gap)/sizeof(gap[0]);
for(int i=0;i<len_gap;++i)
shell_sort(arr,len,gap[i]);
}
Python:
def shell_sort(arr:[int])->[int]:
g = [5,3,1]
for gap in g:
for i in range(gap,len(arr)):
tmp = arr[i]
j = i-gap
while j>=0 and arr[j] > tmp:
arr[j+gap] = arr[j]
j = j - gap
arr[j+gap] = tmp
return arr
快速排序
快速排序的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分：分割点左边都是比它小的数，右边都是比它大的数。
- 时间复杂度：平均:O(nlogn) 最坏:O(n^2)
- 空间复杂度：O(logn)
- 稳定性：不稳定
然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
C:
int division(int *arr,int left,int right)
{
//每次取基准数为最左边的那个数
int base = arr[left];
while(left<right)
{
//从右端开始，向左寻找，找到小于基准数的值时将元素放最左边
while(left<right && arr[right] >= base)
--right;
arr[left] = arr[right];
//同理，当找到时转为左边开始向右找，将大于基准数的值放元素右边
while(left<right && arr[left] <= base)
++left;
arr[right] = arr[left];
}
// 最后将base放到left位置。此时，left位置的左侧数值应该都比left小；
// 而left位置的右侧数值应该都比left大
arr[left] = base;
return left;
}
void quick_sort(int *arr,int left,int right)
{
//左下标要小于右下标，否则会越界
if( left < right)
{
//按照基准数对数组进行分割
int base = division(arr,left,right);
//分别对左右两边进行递归
quick_sort(arr,left,base-1);
quick_sort(arr,base+1,right);
}
}
Python:
def quick_sort(arr:[int],left:int,right:int)->[int]:
def division(arr:[int],left:int,right:int):
base = arr[left]
while left < right:
while left < right and arr[right] >= base:
right -= 1
arr[left] = arr[right]
while left < right and arr[left] <= base:
left += 1
arr[right] = arr[left]
arr[left] = base
return left
if(left<right):
base = division(arr,left,right)
quick_sort(arr,left,base-1)
quick_sort(arr,base+1,right)
return arr
堆排序
堆排序是一种选择排序。
堆是一棵顺序存储的完全二叉树。
- 其中每个结点的关键字都不大于其孩子结点的关键字，这样的堆称为小根堆。
- 其中每个结点的关键字都不小于其孩子结点的关键字，这样的堆称为大根堆。
举例来说，对于n个元素的序列{R0, R1, ... , Rn}当且仅当满足下列关系之一时，称之为堆：
- Ri <= R2i+1 且 Ri <= R2i+2 (小根堆)
- Ri >= R2i+1 且 Ri >= R2i+2 (大根堆)
其中i=1,2,…,n/2向下取整；
- 时间复杂度：O(nlogn)
- 空间复杂度：O(1)
- 稳定性：不稳定
归并排序
该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而**治(conquer)**的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
- 时间复杂度：O(nlog2n)
- 空间复杂度：O(n)
- 稳定性：稳定
基数排序
基本思想：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。
算法步骤：
- 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。
- 从最低位开始，依次进行一次排序。
- 这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
基数排序的方式可以采用 LSD（Least significant digital）或 MSD（Most significant digital），LSD 的排序方式由键值的最右边开始，而 MSD 则相反，由键值的最左边开始。
不妨通过一个具体的实例来展示一下基数排序是如何进行的。 设有一个初始序列为: R {50, 123, 543, 187, 49, 30, 0, 2, 11, 100}。
我们知道，任何一个阿拉伯数，它的各个位数上的基数都是以 0~9 来表示的，所以我们不妨把 0~9 视为 10 个桶。
我们先根据序列的个位数的数字来进行分类，将其分到指定的桶中。例如：R[0] = 50，个位数上是 0，将这个数存入编号为 0 的桶中。
分类后，我们在从各个桶中，将这些数按照从编号 0 到编号 9 的顺序依次将所有数取出来。这时，得到的序列就是个位数上呈递增趋势的序列。
按照个位数排序： {50, 30, 0, 100, 11, 2, 123, 543, 187, 49}。
接下来，可以对十位数、百位数也按照这种方法进行排序，最后就能得到排序完成的序列。
- 时间复杂度：O(dn)
- 空间复杂度：O(n)
- 稳定性：稳定
Comments | 0 条评论