剑指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;
}
更多推荐
快速排序实现方法(剑指offer思路)
发布评论