浅谈数据结构排序算法中的快速排序

        数据结构中的排序算法有：插入类排序、交换类排序、选择排序、堆排序、归并排序、桶排序。而交换类排序包括：冒泡排序和快速排序。

其中：快速排序（不稳定的排序）

特点：序列越无序，效率越高，快速排序是基于原问题分解成多个子问题，再递归地求解各个子问题。

原理：每次选任一元素作为枢轴（一般选第一个元素），将比枢轴小的元素都放到枢轴前面，比枢轴大的元素都移到枢轴后面。（即类比于：每次选一个标兵，比该标兵矮的同学站左边，比标兵高的同学站右边）

注：下列两种方法的排序都是从小到大排序

方法一：采用递归（较为容易理解）

#include <iostream>
#include <stdbool.h>
using namespace std;
#define ElemType int
ElemType array[] = {9,7,8,5,6,4,3,2,1,0};

void QuickSort(ElemType *array,int low,int high){	//快排 
	if(low >= high){	//若待排序序列只有一个元素，返回空 
		return; 
	}
	int i=low;	//i作为指针从左向右扫描 
	int j=high;	//j作为指针从右向左扫描
	int key=array[low];//第一个数作为基准数 
	while(i<j){
		while(array[j] >= key && i<j){	//从右边找小于基准数的元素 （此处由于j值可能会变，所以仍需判断i是否小于j） 
			j--;	//找不到则j减一 
		}
		array[i]=array[j];	//找到则赋值 
		while(array[i]<=key&&i<j){	//从左边找大于基准数的元素 
			i++;	//找不到则i加一 
		}
		array[j]=array[i];	//找到则赋值 
	}
	array[i]=key;	//当i和j相遇，将基准元素赋值到指针i处 
	QuickSort(array,low,i-1);	//i左边的序列继续递归调用快排 
	QuickSort(array,i+1,high);	//i右边的序列继续递归调用快排 
}

int main()
{	
	int length=sizeof(array)/sizeof(*array);
	QuickSort(array, 0,length-1);//执行快速排序子函数
  cout<<"快排序列：";
	for(int i=0;i<length;i++){
		cout<<array[i]<<" ";
	}
	return 0;

}

最好时间复杂度：O(nlogn)

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

空间复杂度：O(nlogn)

赏

谢谢你请我吃糖果！

微信