JZTXT

c++ 快速排序

发布时间 2023-04-12 04:08:33作者: 乘舟凉

快速排序的思想是使某个数在它该在的位置，然后对这个数前后两部分进行递归处理即可
例子： 6 5 79 2
6该在的位置应该在第三位 5 2 6 79
那么如何使一个数在它该在的位置呢，观察上面的例子，要使一个数在它该在的地方应该要让所有小于它的数在左边，所有大于它的数在右边即可
按照上面的思想我们可以编写代码

#include <iostream>
using namespace std;

#define N 13

template<class T>
void fastSort(T *ary,size_t len);

int main(){
	int ary[] = {4,5,7,2,46,41,4,45,4,56,64,6,4};
	fastSort(ary,N);

	for(int i = 0;i<N;i++){
		cout << ary[i] << " ";	
	}

	return 0;
}


template<class T>
void fastSort(T *ary,size_t len){
	T* t  = new T[len];
	int left = 0,right = len-1;	
	for(int i=1;i<len;i++){
		if(ary[i] < ary[0]){ //我们干脆每次都选定最左边的数为中心节点
			t[left] = ary[i];
			left++;
		}
		else{
			t[right] = ary[i];
			right--;
		}

	}

	t[left] = ary[0];
	memcpy(ary,t,sizeof(T)*len);

	delete[] t;

	if(left>1)
		fastSort(ary,left);
	size_t right_len = len-left-1; //计算右半部分的长度
	if(right_len>1)
		fastSort(ary+left+1,right_len);
}