排序算法.md

排序算法

冒泡排序

#include <stdio.h>

#define length 10

/*
 *冒泡排序，时间复杂度为n的2次方
 * */

void maopao_sort(int arr[], int n){
		for (int i = 0; i < n; i++){
				for (int j = n-1; j > i; j--){
						if (arr[j] > arr[j-1]){
							int temp = arr[j];
							arr[j] = arr[j-1];
						    arr[j-1] = temp;	
						}
				}
		}
}

//高效版本，如果上次没有得到转换，则不进行下次的排序
void maopao_sort2(int arr[],int n){
		int flag;
		for (int i = 0; i < n-1; i++){
				flag = 0;
				for (int j = n-1; j > i; j--){
						if (arr[j] > arr[j-1]){
							int temp = arr[j];
							arr[j] = arr[j-1];
						    arr[j-1] = temp;	
							flag = 1;
						}
				}
				if (flag == 0){
						printf("跳出位置：%d\n",i);
						break;
				}
		}

}

int main(){
		int arr[length] = {5,4,3,2,6,1,7,8,9,10};
		printf("按照从大到小排序，未排序前：\n");
		for(int i = 0; i < length; i++){
				printf(" %d ",arr[i]);
		}
		printf("\n");
		maopao_sort2(arr,length);
		printf("冒泡排序后\n");
		for(int i = 0; i < length; i++){
				printf(" %d ",arr[i]);
		}
		printf("\n");
		return 0;
}

快排序

#include <stdio.h>

#define length 10

/*
 *快排序，使用的归并法。
 快速排序稳定性
 快速排序是不稳定的算法，它不满足稳定算法的定义。
 算法稳定性 -- 假设在数列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的！
 快速排序时间复杂度
 快速排序的时间复杂度在最坏情况下是O(N2)，平均的时间复杂度是O(N*lgN)。
 这句话很好理解：假设被排序的数列中有N个数。遍历一次的时间复杂度是O(N)，需要遍历多少次呢？至少lg(N+1)次，最多N次。
 (01) 为什么最少是lg(N+1)次？快速排序是采用的分治法进行遍历的，我们将它看作一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的定义，它的深度至少是lg(N+1)。因此，快速排序的遍历次数最少是lg(N+1)次。
 (02) 为什么最多是N次？这个应该非常简单，还是将快速排序看作一棵二叉树，它的深度最大是N。因此，快读排序的遍历次数最多是N次。
 * */

void kuai_sort(int arr[],int l, int r){
		if (l < r){
				int i = l;
				int j = r;
				int x = arr[l];
				while(i < j){
						while(i < j && arr[j] < x){ //arr[j] < x用于从大到小排序， > 是从小到大，下个while倒过来
								j--;
						}		
						if (i < j){
								arr[i] = arr[j];
								i++;
						}
						while(i < j && arr[i] > x){
								i++;
						}
						if (i < j){
								arr[j] = arr[i];
								j--;
						}
				}
				arr[i] = x;
				kuai_sort(arr, l,i-1);
				kuai_sort(arr, i+1, r);
		}
}

int main(){
		int arr[length] = {0,1,2,3,4,5,6,7,8,9};
		kuai_sort(arr, 0, length-1);
		for(int i = 0; i < length; i++){
				printf(" %d ",arr[i]);
		}
		printf("\n");
}

归并排序

#include <stdio.h>
#include <stdlib.h>

#define length 10

void guibing(int arr[], int start, int end, int mid){
		int *temp = (int *)malloc((end-start+1)*sizeof(int));
		int i = start;		//数组上半部分的下标
		int j = mid + 1;	//数组下半部分的下标
		int k = 0;			//temp的下标
		while(i <= mid && j <= end){
				if (arr[i] < arr[j]){
						temp[k++] = arr[j++];
				} else {
						temp[k++] = arr[i++];
				}
		}
		while(i <= mid){
				temp[k++] = arr[i++];
		}
		while(j <= end){
				temp[k++] = arr[j++];
		}
		for (int i = 0; i < k; i++){
				arr[start+i] = temp[i];
		}
		free(temp);
}

void guibing_uptodown(int arr[], int start, int end){
		if (arr == NULL || end <= start){
				return;
		}
		int mid = (end+start)/2;
		guibing_uptodown(arr,start,mid);
		guibing_uptodown(arr,mid+1,end);
		guibing(arr,start,end,mid);
}

int main(){
		int arr[length] = {1,2,3,4,5,6,7,8,9,0};
		guibing_uptodown(arr,0,length-1);
		for(int i = 0; i < length; i++){
				printf(" %d ",arr[i]);
		}
		printf("\n");
}

总结

参考：https://labuladong.gitbook.io/algo/di-ling-zhang-bi-du-xi-lie/er-cha-shu-xi-lie-1

快速排序就是个二叉树的前序遍历，归并排序就是个二叉树的后续遍历。

快速排序的逻辑是，若要对 nums[lo..hi] 进行排序，我们先找一个分界点 p，通过交换元素使得 nums[lo..p-1] 都小于等于 nums[p]，且 nums[p+1..hi] 都大于 nums[p]，然后递归地去 nums[lo..p-1] 和 nums[p+1..hi] 中寻找新的分界点，最后整个数组就被排序了。

再说说归并排序的逻辑，若要对 nums[lo..hi] 进行排序，我们先对 nums[lo..mid] 排序，再对 nums[mid+1..hi] 排序，最后把这两个有序的子数组合并，整个数组就排好序了。