• 快速排序

快速排序

• 首先取出一个key，一般取第一个元素
• 从后往前遍历，如果数组中的数据小于了key，那么就将从前往后未比较过的第一个位置即fisrt位置替换为该数据
• 然后从前往后遍历，如果数组中的数据大于了key，那么就将从后往前的第一个比较过数据位置替换
• 直到左右两边的位置重合，说明key就找到了正确的位置，每次循环就能找到一个数的正确位置
• 然后将key左右两边的数据分为两组，递归调用自己。

#include <stdio.h>

void quickSort(int *array, int left, int right)
{
	if(left < right)
	{
		int pivot = array[left];
		int low = left, high = right;
		while(low < high)
		{
			while(array[high] >= pivot && low < high)
				high--;
			array[low] = array[high];
			
			while(array[low] <= pivot && low < high)
				low++;
			array[high] = array[low];
		}
		array[low] = pivot;
		
		quickSort(array, left, low - 1);
		quickSort(array, low + 1, right);
	}
}
 

int main()
{
	int a[] = {1,2,3,5,7};
	
	quickSort(a,0,5);
	
	for(int i=0;i<5;i++){
		printf("%d",a[i]);
	}
	
   /* 我的第一个 C 程序 */
   printf("Hello, World! \n");
   
   return 0;
} 

#include <stdio.h>

int partion(int *array, int left, int right){
	int pivot = array[left];
		int low = left, high = right;
		while(low < high)
		{
			while(array[high] >= pivot && low < high)
				high--;
			array[low] = array[high];
			
			while(array[low] <= pivot && low < high)
				low++;
			array[high] = array[low];
		}
		array[low] = pivot;
	return low;
}

void quickSort(int *array, int left, int right)
{
	if(left < right)
	{
		int low = partion(array,left,right);
		printf("%d \n",low);
		quickSort(array, left, low - 1);
		quickSort(array, low + 1, right);
	}
}
 

int main()
{
	int a[] = {1,2,3,5,7,8,4,1};
	
	quickSort(a,0,7);
	
	for(int i=0;i<8;i++){
		printf("%d",a[i]);
	}
	
   /* 我的第一个 C 程序 */
   printf("Hello, World! \n");
   
   return 0;
}  

快速排序是一种不稳定排序，它的时间复杂度为O(n·lgn)，最坏情况为O(n2)；空间复杂度为O(n·lgn)。
这种排序方式是对于冒泡排序的一种改进，它采用分治模式，将一趟排序的数据分割成独立的两部分，其中一组数据的每个值都小于另一组。每一趟在进行分类的同时实现排序。

参考：
https://blog.csdn.net/starzyh/article/details/90272347
https://blog.csdn.net/qq_43049618/article/details/101618958
https://blog.csdn.net/qq_40527383/article/details/98514300
https://rebright.blog.csdn.net/article/details/76236562