算法導論第四章-快速排序

//快速排序複雜度為O(nlogn)，平均複雜度也是O(nlogn)，是以就平均時間而言，被認為是最好的一種排序方法

#include<iostream>
using namespace std;

//以a[low]為樞軸，小于它的都放到a[low]前面，大于它的都放到後面，則low的位置即确定
int quick_sort(int *a,int low,int high)
{
	int tmp=a[low];
	int i=low;
	int j=high;
	while(i<j)
	{
		//從後開始周遊，直到找到比樞軸小的
		while(i<j&&a[j]>=tmp)
			j--;
		//找到之後把它放到前面
		if(i<j)
		{
			a[i]=a[j];
			i++;
		}
		//再從i開始向後周遊，直到找到比樞軸大的
		while(i<j&&a[i]<=tmp)
			i++;
		//找到之後把發放到j處
		if(i<j)
		{
			a[j]=a[i];
			j--;
		}
	}
	//确定i的位置
	a[i]=tmp;
	return i;
}

//遞歸排序
void sort(int *a,int low,int high)
{
	if(low<high)
	{
		int i=quick_sort(a,low,high);
		sort(a,low,i);
		sort(a,i+1,high);
	}
}
int main()
{
	int a[ ]={2,1,3,4,7,5,8,6,0,9};
	int length=sizeof(a)/sizeof(*a);
	cout<<"原數組為：          ";
	for(int i=0;i<length;i++)
		cout<<a[i]<<" ";
	cout<<endl;

	sort(a,0,length-1);

	cout<<"快速排序後的數組為：";
	for(int i=0;i<length;i++)
		cout<<a[i]<<" ";
	cout<<endl;
	return 0;
}
           

算法導論書上的方法：

#include <iostream>
#include <vector>

using namespace std;


//注意begin和end 為下标,以第一個數begin為樞軸
void quick_sort(vector<int> &data , int begin , int end)
{
	if(data.empty() || begin >= end)
		return ;

	int j = begin ;

	for(int i = begin + 1; i <= end ; i++)
	{
		if(data[i] < data[begin])
		{ 
			j++;
			swap(data[i] , data[j]);
		}
	}
	swap(data[j] , data[begin]);
	quick_sort(data , begin , j - 1);
	quick_sort(data , j + 1 , end);
}

int main()
{
	int num[] = {2,4,1,6,8,3,0,5};
	int len = sizeof(num) / sizeof(*num);
	vector<int> data(num , num + len);//注意data的初始化方式
	quick_sort(data , 0 , len - 1);
	for(int i = 0 ; i < len ; i++)
	{
		cout<<data[i]<<" ";
	}
	cout<<endl;
}