[数据结构与算法]常见排序算法

几个基础概念:

稳定：如果原数组中a在b的前面a与b相等，且排序之后a仍然在b的前面，称为该算法稳定。否则为不稳定。

排序算法中经常用到排序的起始位置和数组长度以及交换操作。

注意：有些传入函数的参数是数组和数组长度，而有一些是数组和左下标及右下标。

//起始位置
int start = 0;
//数组长度
int length = sizeof(arr)/sizeof(int);

//交换两个数值的函数
void swap(int &a,int &b){
	int temp = a;
	a = b;
	b = temp;
}

1.冒泡排序bubble sort

通过对待排序序列从前到后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素之间从前部移到后部。前后两个指针，每一轮确定当前的最大值位置。

逆序交换

时间复杂度：O(n^2)。

空间复杂度：O(1)。

是否稳定：稳定。

void bubble_sort(int arr[],int length){
	for(int i = 0;i<length;i++){
		for(int j = 0;j < length;j++){
			if(q[i] > q[j]) swap(q[i],q[j]);
		}
	}
}

调用方法：

bubble_sort(arr, length);

2.选择排序selection sort

第一次找出arr[0,n-1]中确定最小值和arr[0]交换，第二次找出arr[1,n-1]中确定最小值和arr[1]交换......

最小值交换

时间复杂度：O(n^2)

空间复杂度：O(1)

是否稳定：不稳定

void selection_sort(int arr[],int length) {
	int min ;
	//事实上遍历length-1次也是可以的
	for (int i = 0; i < length ; i++) {
		//每次找到从i+1到length的最小值
        min = i;
		for (int j = i + 1; j < length; j++) {
			if (arr[min] > arr[j]) min = j;
		}
		swap(arr[min], arr[i]);
	} 
}

3.快速排序

快速排序先找到一个基准值，使得数组分为两部分：左边都是小于该基准值的数，右边都是大于该基准值的数。然后对左右两部分再以同样的方法排序。

时间复杂度：O(nlogn)

空间复杂度：O(1)

是否稳定：不稳定

void quick_sort(int arr[], int left, int right) {
	if (left >= right)return;
	int i = left - 1, j = right + 1;
    //以中间点作为基准值
	int x = arr[(left + right) / 2];
	while (i < j) {
		do i++; while (arr[i] < x);
		do j--; while (arr[j] > x);
        //左边大于x的数和右边小于x的数交换
		if (i < j)swap(arr[i], arr[j]);
	}
    //分别对左右两边以同样的方法排序，注意边界
	quick_sort(arr, left, j);
	quick_sort(arr, j + 1, right);
}

调用方法：注意这里的 left 和 right 是下标，尤其是 right 需要 length-1.

quick_sort(arr,start,length-1)

4.归并排序merge sort

归并排序基于分治思想，首先确定分界点，然后递归排序左边和右边，最后再把两个部分合并起来。归并排序需要一个中间数组。

时间复杂度：O(nlogn)

空间复杂度：O(n)

是否稳定：稳定

//额外数组
int temp[N];
void merge_sort(int arr[], int left, int right) {
	if (left >= right)return;
	//确定分界点
	int mid = (left + right) / 2;
	//递归排序left right
	merge_sort(arr, left, mid), merge_sort(arr, mid + 1, right);
	//归并合二为一
	int k = 0, i = left, j = mid + 1;
	while (i <= mid && j <= right) {
		if (arr[i] < arr[j])temp[k++] = arr[i++];
		else temp[k++] = arr[j++];
	}
	while (i <= mid)temp[k++] = arr[i++];
	while (j <= right)temp[k++] = arr[j++];
	//复制回去
	for (i = left, j = 0; i <= right; i++, j++) {
		arr[i] = temp[j];
	}

}

调用方法：

merge_sort(arr,start,length-1);

5.插入排序insertion sort

插入排序类似于扑克牌的整理，先把下标为0的数看成是有序的，从下标为1的数开始与前一个数相比较。只要比前面的数值小就要往前排。

时间复杂度：O(n^2)

空间复杂度：O(1)

是否稳定：稳定

void insertion_sort(int arr[], int length) {
	for (int i = 0; i < length ; i++) {
		for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
			swap(arr[j], arr[j - 1]);
		}
	}
}

void insertion_sort2(int arr[], int length) {

	for (int i = 1; i < length; i++) {
		//先保存要插入的数
		int insertVal = arr[i];
		int insertIdx = i-1;
		//只要不越界并且满足要插入的数小于前面的数
		while (insertIdx>=0&&insertVal<arr[insertIdx]) {
			arr[insertIdx++] = insertVal;
			insertIdx--;
		}
		//当退出循环时说明插入的位置是insertIdx+1
		arr[insertIdx + 1] = insertVal;
	}
}

6.堆排序heap sort

先把数组构造成一个大顶堆（父节点大于子节点），然后把堆顶（数组最大值，数组第一个元素）和数组最后一个元素交换，这样就把最大值放到了数组最后边。把数组长度减一，在进行构造堆。

时间复杂度：O(nlogn)

空间复杂度：O(1)

是否稳定：不稳定

void adjust_heap(int a[], int x, int n)
{
    //x是待调整结点的下标，n是待调整的最后一个元素的下标
	int l = x * 2 + 1;//左子结点的下标
	int r = x * 2 + 2;//右子结点的下标
	int max = x;

	if (l < n && a[l] > a[max]) max = l;
	if (r < n && a[r] > a[max]) max = r;

	if (max != x)
	{
		swap(a[x], a[max]);
		adjust_heap(a, max, n);
	}
}

void heap_sort(int arr[], int length)
{
	for (int i = length / 2 - 1; i >= 0; i--)
		adjust_heap(arr, i, length); //建初始堆

    //进行n-1次排序
	for (int i = length - 1; i > 0; i--)
	{
		swap(arr[0], arr[i]);   //根结点与最后一个元素交换
		adjust_heap(arr, 0, i); //对数组重新建堆
	}
}

7.计数排序

桶思想的一种，是一种非比较排序，将整数按位数切割成不同的数字，然后按每个位数分别比较。适用于整数数字量很大但是数值的范围小且已知的情况下。开辟一个数组，数组的下标作为代表的值，array[ i ]表示在数值 i 有array[ i ]个。

例：某大型企业员工的年龄排序，快速得知高考名次。

时间复杂度：O(n)

void bucket_sort(int arr[], int length) {
	//这里设arr数组的数值范围在[0,100]则需要开辟一个101个值的数组
	//并且初始化为不在数值范围的数
	int count[103] = {0};
	//计数
	for (int i = 0; i < length; i++) count[arr[i]]++;
	//再把临时数组的值赋给原数组
	int count_size = sizeof(count) / sizeof(int);
	for (int i = 0, j = 0; i < count_size; i++) {
		while (count[i]-- > 0)arr[j++] = i;
	}
}

8.希尔排序shell sort

是基于插入排序的一种更高效的排序方法，也称为缩小增量排序。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序。随着增量逐渐减少，每组包含的关键词越来越多，当增量减到1整个数组正好分成一组，算法终止。

时间复杂度：

空间复杂度：

是否稳定：

①基于交换的希尔排序：找到一个就交换一个。

void shell_sort1(int arr[], int length) {
	int temp = 0;
	//每次一组的大小为一半
	for (int gap = length / 2; gap > 0; gap /= 2) {
		//下标i和下标j的数分别表示对比的两组
		//遍历各组中所有元素（共gap组，每组为length/gap个数据）步长gap
		for (int i = gap; i < length; i++) {
			for (int j = i - gap; j >= 0; j -= gap) {
				//如果当前元素大于加上步长后的那个元素，交换
				if (arr[j] > arr[j + gap])swap(arr[j], arr[j + gap]);
			}
		}
	}
}

②基于移位的希尔排序（更快）

void shell_sort2(int arr[],int length) {

	//增量每次都/2
	for (int step = length / 2; step > 0; step /= 2) {

		//从增量那组开始进行插入排序，直至完毕
		for (int i = step; i < length; i++) {

			int j = i;
			int temp = arr[j];
			//arr[j]和arr[j-step]是要移动的一组数
			while (j - step >= 0 && arr[j - step] > temp) {
				arr[j] = arr[j - step];
				j = j - step;
			}
			//循环结束则找到那个temp的位置。
			arr[j] = temp;
		}
	}
}