快速排序的思想很简单,注意实现的时候一定要考虑周全:
快排思想:分治递归的思想!!
选取枢纽元pivot很是关键,我是直接用的第一个数组元素;
初始化i为第一个元素,j为最后一个元素;
首先j从后往前遍历,寻找第一个比枢纽元小的元素,将其交换到i小标所在位置;然后i从前往后遍历寻找第一个比pivot大的元素,将其交换到j下标所在的位置; 始终注意i<j这一循环终止条件;
代码如下:
1 #include<iostream> 2 using namespace std; 3 int partision(int *arr, int left, int right) 4 { 5 if (left == right) 6 return left; 7 int pivot = arr[left]; 8 int i = left, j = right; 9 while (i<j) 10 { 11 while (i<j&&arr[j]>=pivot) 12 --j; 13 arr[i] = arr[j]; 14 while (i<j&&arr[i] <= pivot) 15 ++i; 16 arr[j] = arr[i]; 17 } 18 arr[j] = pivot; 19 return j; 20 } 21 void quickSort(int *arr, int left, int right) 22 { 23 if (left < right)//晕,之前漏掉了这一句,一直在苦苦的调试!!!若是相等,说明就只有一个元素了,直接返回就好了嘛 24 { 25 int mid = partision(arr, left, right); 26 quickSort(arr, left, mid - 1); 27 quickSort(arr, mid + 1, right); 28 } 29 } 30 31 int main() 32 { 33 int arr[10] = { 8, 2, 7, 4,15,1,9,8,22,6}; 34 quickSort(arr, 0, 9); 35 for (int i = 0; i < 10; ++i) 36 cout << arr[i] << " "; 37 return 0; 38 }