快速排序--15--快排--LeetCode排序数组
排序数组
给定一个整数数组 nums
,将该数组升序排列。
示例 1:
输入:[5,2,3,1] 输出:[1,2,3,5]
示例 2:
输入:[5,1,1,2,0,0] 输出:[0,0,1,1,2,5]
提示:
1 <= A.length <= 10000
-50000 <= A[i] <= 50000
1 class Solution { 2 public: 3 int LOW;//原始数组的左边界 4 int HIGH;//原始数组的右边界 5 vector<int> num;//原始数组复制后用来操作的新数组 6 int Partition(int low,int high){//寻找分界线下标 7 int temp = num[low];//在原始数组中随机取一个数出来,留出一个空位置 8 while(low < high){ 9 while(low<high&&num[high] >= temp)//右边的数要大于等于原来空位置上的数则,右边界左移 10 --high; 11 num[low] = num[high];//把右边第一个小于那个原来空位置上的数放到空位置上去,腾出了一个新的空位置 12 while(low<high&&num[low] <= temp)//左边的数要小于等于原来空位置上的数则,左边界右移 13 ++low; 14 num[high] = num[low];//把左边第一个大于那个原来空位置上的数放到新的空位置上去,腾出了一个新的空位置 15 }//此时,以low下标为分界线,low的左边的数都比随机取出的数temp要小,low的右边的数都比随机取出来的数temp要大 16 num[low] = temp;//把随机取出来的数放到分界线下标的空位置上去 17 return low;//返回分解线的下标 18 } 19 void quickSort(int low,int high) { 20 if(low < high){ 21 int key = Partition(low,high);//将数组分为两部分
22 quickSort(low,key - 1);//将前半部分再进行快排 23 quickSort(key + 1,high);//将后半部分再进行快排 24 } 25 } 26 vector<int> sortArray(vector<int>& nums) {//入口函数 27 LOW = 0; 28 HIGH = nums.size() - 1; 29 num = nums; 30 quickSort(LOW,HIGH); 31 return num; 32 } 33 };
版权声明:本文为qinqin-me原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。