排序算法

本文整理了十大经典排序算法的代码以及复杂度分析

冒泡排序

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)