c++十大排序——快速排序

算法基本知识铺垫

有些人可能不知道什么是稳定排序、原地排序、时间复杂度、空间复杂度，我这里先简单解释一下：

1、稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 仍然在 b 的前面，则为稳定排序

2、非稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 可能不在 b 的前面，则为非稳定排序。

3、原地排序：原地排序就是指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储 空间进行比较和交换的数据排序。

4、非原地排序：需要利用额外的数组来辅助排序。

5、时间复杂度：一个算法执行所消耗的时间。

6、空间复杂度：运行完一个算法所需的内存大小

十大排序一览图

十大排序中的稳定排序

冒泡排序（bubble sort） — O(n2)

插入排序 （insertion sort）— O(n2)

归并排序 （merge sort）— O(n log n)

十大排序中的非稳定排序

面试考察中一般问快排，选择，希尔，堆这几种非稳定排序

选择排序 selection sort）— O(n2)

希尔排序 （shell sort）— O(n log n)

堆排序 （heapsort）— O(n log n)

快速排序 （quicksort）— O(n log n)

快速排序

快速排序算法_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1at411T75o?spm_id_from=333.337.search-card.all.click具体思想参考up主讲的，很清晰，这里就只给出了代码，以后有时间再回来补上

************************************2022.5.30************************************************

算法思路

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序算法通过多次比较和交换来实现排序，其排序流程如下：

1、首先设定一个分界值，通过该分界值将数组分成左右两部分。

2、将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。

3、然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

4、重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

概括来说为 挖坑填数 + 分治法。

图解算法

快速排序主要有三个参数，left 为区间的开始地址，right 为区间的结束地址，Key 为当前的开始的值。

第一步

key 首先与 arr[right] 进行比较，如果 arr[right]<key，则arr[left]=arr[right]将这个比key小的数放到左边去，如果arr[right]>key则我们只需要将right--，right--之后，再拿arr[right]与key进行比较，直到arr[right]<key交换元素为止。

 第二步

如果右边存在arr[right]<key的情况，将arr[left]=arr[right]，接下来，将转向left端，拿arr[left ]与key进行比较，如果arr[left]>key,则将arr[right]=arr[left]，如果arr[left]<key，则只需要将left++,然后再进行arr[left]与key的比较。

第三步 

然后再移动right重复上述步骤。

************************************2022.5.30************************************************

#include<iostream>

using namespace std;

void quickSort(int arr[], int begin, int end) {
	if (begin >= end) return;
	int left = begin;
	int right = end;
	int temp = arr[left];

	while (left < right) {
		//从后往前找比他小的放前面，从前往后找比它大的放后面
		//以第一个数为基准，必须先从后往前走，再从前往后走
		while (left < right && arr[right] >= temp) {
			right--;
		}  //跳出此循环，代表right找到了比temp小的数字，所以此时arr[left]=arr[right]
		if (left < right) {
			arr[left] = arr[right];
		}
		while (left < right && arr[left] <= temp) {
			left++;
		}//同理
		if (left < right) {
			arr[right] = arr[left];
		}
		if (left == right) {
			arr[left] = temp;
		}
	}
	quickSort(arr, begin, left - 1);
	quickSort(arr, left + 1, end);
}
int main() {

	int arr[11] = { 5,6,3,2,7,8,9,1,4,0,0 };
	quickSort(arr, 0, 10);
	for (auto x : arr) {
		cout << x << " ";
	}
	return 0;
}