C++实现快速排序

x33g5p2x  于11个月前 转载在 C/C++  
字(0.9k)|赞(0)|评价(0)|浏览(142)

一,快速排序说明

举例:

21,25,49,26,16,8

选择第一个元素21为中心元素,将比21小的元素放到前面,比21大的元素放到后面,则调整为:8,16,21,25,49,26

对21之前的元素进行如上操作,则之前的部分调整为:8,16。无法再调整;
对21之后的元素进行如上操作,则之后的部分调整为:25,49,26。25之前无元素,则继续对25之后的元素进行如上操作,调整为:26,49,无法再调整。

排序完成。

二,快速排序实现

#include<iostream>
using namespace std;

void QSort(int arry[], int low, int size)
{
	int high = size-1;
	if(low<high)
	{
		int x = arry[low];  //取第一个数据元素为枢纽元素,则该位置空出来 
		int index = low;    //记录空出来的位置 
		while(low<high)
		{
			while(arry[high]>=x&&high>low)  //从后往前寻找比枢纽元素小的元素 
	        {
	        	high--;
			}
			arry[index] = arry[high];  //找到比枢纽元素小的元素后将其补充到空位中,出现了一个新的空位 
			index = high;
			
			while(arry[low]<=x&&high>low)  //从前往后寻找比枢纽元素大的元素 
			{
				low++;
			}
			arry[index] = arry[low];  //找到比纽元素大的元素后将其补充到空位中,出现了一个新的空位 
			index = low;
		}
		arry[low] = x;
		QSort(arry,0, index);  //对枢纽元素左半部分和右半部分分别进行快速排序 
		QSort(arry,index+1,size);
	}
}

int main()
{
	int a[] = {81,94,11,96,12,35,17,95,28,58,41,75,15};
	QSort(a,0,13);
	for(int i=0; i<13; ++i)
	{
		cout << a[i] << " ";
	}
}

相关文章