学步园

1、递归实现

#include<iostream><br /> using namespace std;<br /> void QuickSort(int arr[], int low, int high);<br /> inline void Swap(int &a, int &b)<br /> {<br /> int temp = a;<br /> a = b;<br /> b = temp;<br /> }</p> <p>int main()<br /> {<br /> int arr[] = {65, 70, 75, 80, 85, 60, 55, 50, 45};<br /> int n = sizeof(arr) / sizeof(int);<br /> cout<<"排序前为:";<br /> for(int i=0; i<n; i++)<br /> cout<<arr[i]<<" ";<br /> cout<<endl;<br /> QuickSort(arr, 0, n-1);<br /> cout<<"排序后为:";<br /> for(int i=0; i<n; i++)<br /> cout<<arr[i]<<" ";<br /> cout<<endl;<br /> return 0;<br /> }</p> <p>void QuickSort(int arr[], int low, int high)<br /> {<br /> if(low > high)<br /> return;<br /> int i = low;<br /> int j = high;<br /> int target = arr[low]; //选取低位low位置的元素作为目标元素<br /> while(i < j)<br /> {<br /> while(j>i && arr[j]>target)<br /> j--;<br /> if(j<=i)<br /> break;<br /> while(i<j && arr[i]<=target)<br /> i++;<br /> if(i>=j)<br /> break;<br /> Swap(arr[i], arr[j]); //交换<br /> j--;<br /> i++;<br /> }<br /> Swap(arr[low], arr[j]); //将low位的目标元素放到正确位置<br /> QuickSort(arr, low, j-1);<br /> QuickSort(arr, j+1, high);<br /> }