题解 | #排序#

class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 将给定数组排序
* @param arr int整型vector 待排序的数组
* @return int整型vector
*/
void swap(vector&arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
void quicksort(vector& arr, int left, int right){
//快速排序
if(left >= right) return;
else if(left < right){
//找到分割点
int pos = partition(arr, left, right);
//对左边进行快排
quicksort(arr, left, pos-1);
//对右边进行快排
quicksort(arr, pos+1, right);
}
}
int partition(vector&arr, int left, int right){
int first = arr[left];
while(left < right){
while(left < right && arr[right] > first) {
right --;
}
if(left < right){
swap(arr, left, right);
}
while(left < right && arr[left] < first) {
left++;
}
if(left < right){
arr[right] = arr[left];
right --;
}
arr[left] = first;
}
return left;
}
void Bubblesort(vector& arr){
//冒泡排序
//超时
for(int i=arr.size()-1; i>0; i--){
for(int j=0; j<i; j++){
if(arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
vectorMySort(vector& arr) {
// 调用库函数： sort(arr.begin(), arr.end());
// 冒泡排序：超时 Bubblesort(arr);
// 快速排序
int left = 0;
int right = arr.size()-1;
quicksort(arr, left, right);

    return arr;
}
};