排序算法
本文整理了十大经典排序算法的代码以及复杂度分析
冒泡排序
void bubbleSort(int num[],int n){
int t;
//排序n - 1次
for(int i = 2;i <= n;i++){
int tmp = n - i;
//第一次排序时j最大要到n - 2，第二次时j要到n - 3...以此类推，最大要到n - i
for(int j = 0;j <= tmp;j++){
if(num[j] > num[j + 1]){
t = num[j];num[j] = num[j + 1]; num[j + 1] = t;
}
}
}
}
改进：如果在一次循环中没有出现元素的交换，即某一次i = k(2 <= k <= n)时，在j的循环中都是num[j] < num[j + 1]，那么说明数组中元素已经是升序，不需要再进行后续的循环操作了
void bubbleSort(int num[],int n){
int flag;
int t;
//排序n - 1次
for(int i = 2;i <= n;i++){
flag = 1;
int tmp = n - i;
for(int j = 0;j <= tmp;j++){
if(num[j] > num[j + 1]){
t = num[j];num[j] = num[j + 1]; num[j + 1] = t;
flag = 0;
}
}
if(flag == 1) return;
}
}
时间复杂度：O(n²)
空间复杂度：O(1)，只需要两个整型变量
选择排序
void selectSort(int num[],int n){
//每次寻找i往后中最小的元素，然后将其与i下标对应元素交换位置
for(int i = 0;i < n - 1;i++){
int tmp = num[i];
int minIndex = i;
for(int j = i + 1;j < n;j++){
if(num[j] < tmp){
minIndex = j;
tmp = num[j];
}
}
int t = num[i];
num[i] = num[minIndex];
num[minIndex] = t;
}
}
时间复杂度：O(n²)
空间复杂度：只需要两个整型变量
桶排序
void bucketSort(int num[],int n){
int tmp[100] = {0}; //排序0到99数字
for(int i = 0;i < n;i++){
tmp[num[i]] += 1;
}
int index = -1;
for(int i = 0;i < 100;i++){
while(tmp[i] > 0){
num[++index] = i;
tmp[i]--;
}
}
}
时间复杂度：O(n)，第一个for循环执行了n次，第二个for循环中的while语句中的"tmp[i] > 0"语句也是执行了n次(不包含当每次tmp[i]减为0时再执行的那一次，因为这与数组中的数有关，当数值大小越离散，如1，2，3，4，5…(集中，如1，1，1，1，1…)，就会出现更多次tmp[i]减为0的时候)。所以是O(n + n)，即O(n)
空间复杂度：O(k)，k为数组中数的大小范围，所以可以看出来，如果数组中的数的大小差距过大(如1到1000)，那么就需要的空间就更大，越浪费
快速排序
void quickSortt(int num[],int l,int r){
if(l >= r) return;
int ll = l,rr = r;
//选择最左端元素为基准
int tmp = num[l];
while(ll != rr){
while(ll < rr && num[rr] >= tmp) rr--;
while(ll < rr && num[ll] <= tmp) ll++;
if(ll < rr){
int t = num[ll];
num[ll] = num[rr];
num[rr] = t;
}
}
//单次排序的结果是基准数来到他在最终排序结果中应该处于的位置，然后基准数往左的数都小于它，往右的数都大于他
num[l] = num[ll];
num[ll] = tmp;
//对基准数左右两边递归进行同样的排序操作
quickSortt(num,l,ll - 1);
quickSortt(num,ll + 1,r);
}
void quickSort(int num[],int n){
quickSortt(num,0,n - 1);
}
时间复杂度：O(nlogn)
堆排序
//堆的调整方法，n为堆的大小，调整pos为根的子树
void shift(int num[],int n,int pos){
while(pos <= n / 2){
int l = pos * 2;
int r = pos * 2 + 1;
if(r <= n && num[r] > num[l]) l = r;
//如果pos节点比左右子树都优先，那么不用调整，直接返回
if(num[pos] > num[l]) return;
int t = num[pos];
num[pos] = num[l];
num[l] = t;
pos = l;
}
}
/*堆排序，n为数组的大小。在堆中使用的是顺序存储结构，所以节点下标从1开始更好，这样当前节点下标乘以2以及乘以2加一就是左右儿子的下标，所以正式开始排序之前创建一个比待排序数组大1的数组作为堆，0号下标空置，对其排序完成后再搬回到函数接收的数组中，返回*/
void heapSort(int a[],int n){
//创建堆所在数组
int num[n + 1];
num[0] = 0;
for(int i = 1;i <= n;i++){
num[i] = a[i - 1];
}
//建堆
for(int i = n / 2;i > 0;i--){
shift(num,n,i);
}
//进行n - 2次排序后，num数组中下标3到n已经是有序，而堆顶的num[1]
//是num[1]与num[2]的较大值，所以直接交换他们，整个num数组就排序完毕了
for(int i = 1;i <= n - 2;i++){
int t = num[1];
num[1] = num[n - i + 1];
num[n - i + 1] = t;
shift(num,n - i,1);
}
int t = num[1];
num[1] = num[2];
num[2] = t;
for(int i = 1;i <= n;i++){
a[i - 1] = num[i];
}
}
时间复杂度：O(nlogn)
归并排序
//二路合并操作
void merge(int a[],int left,int mid,int right){
int tmp[right - left + 1];
//左部分的起始下标为left，右半部分起始下标为mid + 1
int i = left,j = mid + 1,k = -1;
while(i <= mid && j <= right){
if(a[i] <= a[j]) tmp[++k] = a[i++];
else tmp[++k] = a[j++];
}
//如果是左半部分合并完了就把右半部分剩下的全部合并到tmp数组中；右半部分同理
while(i <= mid) tmp[++k] = a[i++];
while(j <= right) tmp[++k] = a[j++];
//合并完把tmp数组拷贝回a数组。注意tmp数组不是malloc()函数分配空间的，不用free()
for(int i = 0;i <= k;i++){
a[left + i] = tmp[i];
}
}
//递归地数组拆分为两个子数组，直到数组只有一个元素；将两个子数组进行二路归并
void mergeSortDivide(int a[],int left,int right){
if(left >= right) return;
int mid = (left + right) / 2;
//[left,mid]分到左部分，[mid + 1,right]分到右部分
mergeSortDivide(a,left,mid);
mergeSortDivide(a,mid + 1,right);
//把两部分合并起来
merge(a,left,mid,right);
}
//==========调用函数=========================//
void mergeSort(int num[],int n){
mergeSortDivide(num,0,n - 1);
}
时间复杂度：O(nlogn)
空间复杂度：O(n)，需要一个临时用于合并的数组
插入排序
void insertSort(int num[],int n){
int tmp,j;
//每次循环将num[i]插入到它前面的序列中应该插入的位置
for(int i = 1;i < n;i++){
tmp = num[i];
for(j = i;j > 0 && num[j - 1] > tmp;j--){
num[j] = num[j - 1];
}
num[j] = tmp;
}
}
希尔排序
//使用增量dk进行直接插入排序(插入排序其实就是增量为1的时候的排序)
void shellInsert(int num[],int n,int dk){
int tmp,j;
for(int i = dk;i < n;i++){
tmp = num[i];
for(j = i;j - dk >= 0 && num[j - dk] > tmp;j -= dk){
num[j] = num[j - dk];
}
num[j] = tmp;
}
}
//=============调用函数==========//
//dk为增量序列，m为序列中的数的个数
void shellSort(int num[],int n,int dk[],int m){
//遍历使用增量序列中的每个增量进行插入排序
for(int i = 0;i < m;i++){
shellInsert(num,n,dk[i]);
}
}
计数排序
计数：计算数组中每一个数的个数，然后根据计数结果得出每个元素应该放的位置。如排序0到99的整数，计数得到0的个数为5，1的个数为6，那么1的存放位置下标应该是10到5
void countSort(int num[],int n){
int tmp[n];
//复制原数组
for(int i = 0;i < n;i++){
tmp[i] = num[i];
}
//计数数组
int count[100] = {0};
//计数
for(int i = 0;i < n;i++){
count[tmp[i]] += 1;
}
for(int i = 1;i < 100;i++){
count[i] = count[i] + count[i-1];
}
//根据计数结果将数放回到原数组
for(int i = 0;i < n;i++){
num[--count[tmp[i]]] = tmp[i];
}
}
时间复杂度：O(n + k)，k为数组中数的大小范围
空间复杂度：O(n + k)，一个用于复制的数组和一个用于计数的数组
基数排序
基数排序看起来很像是对每个数的每一位进行计数排序，最后合并起来
int radix = 10;//基数为10(0到9)
int digitNum = 2;//最多有2位数字
//获取number第i位上的数
int getDigitNum(int number,int i){
while(i > 1){
number /= 10;
i--;
}
return number % 10;
}
//完成对第i位的排序，从num1数组排序到num2数组中
void radixSortt(int num1[],int num2[],int n,int i){
int count[radix];
for(int j = 0;j < radix;j++) count[j] = 0;
for(int j = 0;j < n;j++){
count[getDigitNum(num1[j],i)] += 1;
}
for(int j = 1;j < radix;j++){
count[j] += count[j - 1];
}
//必须从右到左放置被排序数组的元素，因为对上一位的排序已经完成，不能破坏，而count[index]也是从大到小的
for(int j = n - 1;j >= 0;j--){
int index = getDigitNum(num1[j],i);
num2[--count[index]] = num1[j];
}
}
void radixSort(int num[],int n){
//用于放置排序后数据的临时数组，这里num2数组不是使用malloc()函数分配空间的
//最后不能用free()函数释放，包括上面的count数组
int num2[n];
int i = 1;
//对奇数位排序时从num数组排序到num2数组中
//对偶数位排序时从num2数组排序到num数组中
while(i <= digitNum){
if(i % 2 == 1) radixSortt(num,num2,n,i);
else radixSortt(num2,num,n,i);
i++;
}
//最大位数为奇数时，说明最后一次排序后数据是放在num2数组中，要拷贝回num数组
if(digitNum % 2 == 1){
for(int j = 0;j < n;j++) num[j] = num2[j];
}
}
时间复杂度：O(n * m)，其中m为数组中的数的最大位数
空间复杂度：O(n + k)