有多种做法可以写出快速排序,但思路都是一样的,通过选定一个轴值,将数组分为两部分,比轴值小的排在轴值左侧,比轴值大的排在轴值右侧,然后分别对轴值两侧的部分再进行前述操作,直到整个数组有序。
法一:选定数组首位为轴值,分别顺序从右左两侧相向扫描,从右侧扫描时,左指向为轴值,右指向比轴值小则交换左右指向值;从左侧扫描时,右指向为轴值,左指向比轴值大或等于轴值时交换左右指向值,当左右指向相等的时候结束本轮排序,并分别将轴值左右两部分进行下一轮排序,直到整个数组有序。
法二:选定数组首位为轴值,对数组除首位外的剩余数组部分分别进行右左扫描,当右指向值比轴值小、左指向值比轴值大或等于轴值时,交换左右指向值,重复进行此过程直到左右指向相同,然后对轴值和右指向值进行比较,若轴值大于右指向值则交换双方,否则右指向左移一位,原因是当退出循环时,左右指向相同,但指向的值与轴值的大小关系尚未确定,若指向值比轴值大,则可以将指向值作为轴值(此时指向值左侧都比指向值小),否则必须要将指向值与轴值交换。接着将指向左右两侧的数组部分再次进行上述过程,直到整个数组有序。
#include<iostream> using namespace std; //法一 template<typename T> void quickSort(T a[], int start, int end) { if (start >= end) return; int left = start; int right = end; while (left < right) { while (a[right] >= a[left] && left < right) { right--; } if (left < right) { swap(a[left], a[right]); left++; } while (a[right] >= a[left] && left < right) { left++; } if (left < right) { swap(a[left], a[right]); right--; } } quickSort(a, start, left - 1); quickSort(a, left + 1, end); } //法二 template<typename T> void quick_sort(T a[], int start, int end) { if (start >= end) return; int left = start + 1; int right = end; T mid = a[start]; while (left < right) { while (a[right] >= mid && left < right) right--; while (a[left] < mid && left < right) left++; swap(a[left], a[right]); } if (a[start] > a[right]) swap(a[start], a[right]); else right--; quickSort(a, start, right - 1); quickSort(a, right + 1, end); } int main() { while(true) { int n; cin>>n; int* a=new int[n]; for(int i=0;i<n;i++) { cin>>a[i]; } quickSort(a,0,n-1); for(int i=0;i<n;i++) { cout<<a[i]<<" "; } cout<<endl; } return 0; }
prprpr