leetcode系列——基础算法之快速排序
注：本系列只作为学习记录，有任何疑问请友善私聊。
排序算法相对比较简单，这里我只记录快速排序，原因是后面会用到，而且经常在面试中被问到。快速排序是一种递归排序，简单又快。
1.原理简介
一个列表中含有若干个数，要将它变成有序数列（升序或者降序），我们可以思考这样一种方式：以列表中的任意一个数A为基准，大于A则放到A的右边，小于A则放到左边；然后得到一左一右两个子列表，并被A分开，此时分别对左右列表再进行上面的操作，直到不可再分，所有分完之后，再从后往前合并。
啥意思呢？
第一步：选定一个列表中的一个数A，将其余的数与A比较，大的放到右边，小的放到左边
第二步：对左、右两边的子序列分别进行第一步的操作，直到不能再分
第三步：把每一步分好的组按照“左边（小的数）+基准+右边（大的数）合并起来，合并顺序为从最后一步划分开始到第一步划分结束
下面一步步地划分：
Step1.对2——3——1再进行划分，比如选2作为基准，变成1——2——3，不可再分
Step2.对6——5——7——8划分，比如选7，顺序不变
Step3.对2中选6，变成5——6——7——8
Step4.对3中的7——8划分，比如选7，变成7——8
现在划分完后，再从Step4到Step1合并，按照”左+基准+右“的原则
Merge1：7——8
Merge2：5——6——7——8
Merge3：1——2——3
Merge4：1——2——3——4——5——6——7——8
1、下面给出python代码：
def quicksort(list):
if len(list)<1:
return list
left_list = []
right_list = []
for i in list[1:]:
if i < list[0]:
left_list.append(i)
else:
right_list.append(i)
return quicksort(left_list) + [list[0]] + quicksort(right_list)
import random
A=random.sample(range(1,90),20) # 随机产生一个整数列表
print(A)
print(quicksort(A))注意：在函数返回时，基准值必须以列表的形式合并，否则报错：
正确运行结果：
[63, 59, 13, 19, 75, 8, 22, 51, 83, 71, 42, 54, 72, 64, 50, 1, 79, 2, 11, 88]
[1, 2, 8, 11, 13, 19, 22, 42, 50, 51, 54, 59, 63, 64, 71, 72, 75, 79, 83, 88]快速排序顾名思义，就是快，时间复杂度在最好的情况下是 O(nLogn) ,最差的情况是 O(n^2) ，在面试中常被问到。
在上面的代码中，选择了第一个数作为基准，这是比较常用的。
其他还有很多的排序方法，比如经典的冒泡法、插入法、选择法、计数法等，这里不写了，有需要可以以后再写。
比如
参考资料：
《图解LeetCode初级算法（Python版）》——胡松涛
2、C++实现
快速排序：
class Solution {
public:
void sort(vector<int>& nums, int left, int right)
{
if (left > right)
{
return;
}
int L = left;
int R = right;
int flag = (left+right)/2;
swap(nums[flag],nums[left]);
int base = nums[left];
while (L < R)
{
while(base<=nums[R] && L < R)
{
R--;
}
while(base>=nums[L] && L < R)
{
L++;
}
if(L<R)
{
swap(nums[R],nums[L]);
}
}
nums[left] = nums[L];
nums[L] = base;
sort(nums, left, L-1);
sort(nums, L+1, right);
}
vector<int> sortArray(vector<int>& nums)
{
int left = 0;
int right = nums.size() - 1;
sort(nums, left, right);
return nums;
}
};归并排序：
class Solution {
void merge(vector<int>& nums,int left,int right,vector<int>& ans)
{
int mid=(right-left)/2+left;
int i=left,j=mid+1,k=0;
while(i<=mid&&j<=right)
{
if(nums[i]<=nums[j])
ans[k++]=nums[i++];
else ans[k++]=nums[j++];
}
while(i<=mid)
{
ans[k++]=nums[i++];
}
while(j<=right)
ans[k++]=nums[j++];
for(int i=left;i<=right;i++)
nums[i]=ans[i-left];
}
void mergeSort(vector<int>& nums,int left,int right,vector<int>& ans)
{
if(left>=right)
return ;
int mid=(right-left)/2+left;
mergeSort(nums,left,mid,ans);
mergeSort(nums,mid+1,right,ans);
merge(nums,left,right,ans);
}
public:
vector<int> sortArray(vector<int>& nums) {
vector <int> ans(nums.size());
mergeSort(nums,0,nums.size()-1,ans);
return nums;
}
};
//作者：DevinLi
//链接：https://leetcode-cn.com/problems/sort-an-array/solution/shi-da-pai-xu-suan-fa-c-by-devinli-gizk/
//来源：力扣（LeetCode）
文章被以下专栏收录
