c排序算法

最后发布时间:2021-01-19 06:57:14 浏览量:

快速排序

  • 首先取出一个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