快速排序实现方法（剑指offer思路）

剑指offer思路）"/>

快速排序实现方法（剑指offer思路）

快速排序思想

        从参与排序的数组中，选择一个数，把小于这个数的放在左边，大于这个数的放在右边，然后递归操作。

实现算法思路

• 选择最后一个当作参考值，
• 使用small索引当作比这个数小的下标值
• 遍历数组，如果小于参考值，small+1，如果i和small不相等，交换i和small对应下标的数据
• small增加1，和最后一个值交换
• 递归调用比small小的前一部分
• 递归调用比small小的后一部分

#include <iostream>
#include <vector>using namespace std;
void quickSort(vector<int>& arr, int start, int end)
{if((start >= end)){return;}int small = start - 1;for(int index = start; index < end; ++index){if(arr[index] < arr[end]){++small;if(index != small){std::swap(arr[index], arr[small]);}}}++small;std::swap(arr[small], arr[end]);quickSort(arr, start, small-1);quickSort(arr, small+1, end);
}int main(int argc, char** argv)
{std::vector<int> arr{1,3,5,7,8,2,6};quickSort(arr, 0, arr.size()-1);std::copy(arr.begin(), arr.end(), std::ostream_iterator<int>(cout," "));std::cout<<std::endl;return 0;
}