题目描述：
给定你一个长度为 n 的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整个数列。
输出格式
输出共一行，包含 n 个整数，表示排好序的数列。
数据范围
1≤n≤100000
输入样例：
5
3 1 2 4 5
输出样例：
1 2 3 4 5
思路口诀：
一判二定三寻找(i++、j--、交换),四递归左右
思路图示：
算法1:c++版
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;//1e5+10
int q[N];
void quick_sort(int q[], int l, int r) //建议使用
{
if (l >= r) return;
int i = l - 1, j = r + 1, x = q[(l + r + 1)/2];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j)
swap(q[i], q[j]);
}
quick_sort(q, l, i-1);
quick_sort(q, i, r);
}
void quick_sort2(int q[], int l, int r) //建议使用
{
if (l >= r)
return;
int i = l - 1, j = r + 1, x = q[(l + r )/2];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort2(q, l, j);
quick_sort2(q, j+1, r);
}
void quick_sort3(int q[], int l, int r) //Time limit exceed
{
if (l >= r)
return;
int x = q[l],i = l - 1, j = r + 1 ;
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j)
swap(q[i], q[j]);
}
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
}
void quick_sort4(int q[], int l, int r) //Time limit exceed
{
if (l >= r)
return;
int x = q[r],i = l - 1, j = r + 1 ;
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort2(q, l, i-1);
quick_sort2(q, i, r);
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
scanf("%d", &q[i]);
quick_sort(q, 0, n - 1); //quick_sort2也行！
// sort(q,q+n); //STL 、algorithm自带sort函数
for (int i = 0; i < n; i ++ )
printf("%d ", q[i]);
return 0;
}
算法2：java版
import java.io.*;
public class quickSort {
static void quick_sort(int[] q,int l,int r){
if(l>=r)
return;
int x=q[l+r>>1]; //l+r的值右移1位，相当于l+r的值除以2取整。
int i=l-1;
int j=r+1;
while(i<j){
do i++; while (q[i]<x); //简洁：while(q[++i]<x);
do j--; while (q[j]>x); //简洁：while(q[--j]>x);
if(i<j){
int t=q[i];
q[i]=q[j];
q[j]=t;
}
}
quick_sort(q,l,j);
quick_sort(q,j+1,r);
}
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));//Scanner会超时
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
String[] res=br.readLine().split(" ");
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(res[i]);
}
quick_sort(arr, 0, n - 1);
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
br.close();
}
}
时间复杂度及图示：
O(nlog2n)
平均时间复杂度口诀：
* 冒、选、插：O(n²)
* 快、归、堆：O(nlog2n)
* 计数、基数：O(n+k)
* 桶：O(n*k)
其他排序算法：
1、插入排序
void insert_sort()
{
for (int i = 1; i < n; i ++ )
{
int x = a[i];
int j = i-1;
while (j >= 0 && x < a[j])
{
a[j+1] = a[j];
j -- ;
}
a[j+1] = x;
}
}
2、选择排序
void select_sort()
{
for (int i = 0; i < n; i ++ )
{
int k = i;
for (int j = i+1; j < n; j ++ )
{
if (a[j] < a[k])
k = j;
}
swap(a[i], a[k]);
}
}
3、冒泡排序
void bubble_sort()
{
for (int i = n-1; i >= 1; i -- )
{
bool flag = true;
for (int j = 1; j <= i; j ++ )
if (a[j-1] > a[j])
{
swap(a[j-1], a[j]);
flag = false;
}
if (flag)
return;
}
}
4、希尔排序
void shell_sort()
{
for (int gap = n >> 1; gap; gap >>= 1)
for (int i = gap; i < n; i ++ )
{
int x = a[i];
int j;
for (j = i; j >= gap && a[j-gap] > x; j -= gap)
a[j] = a[j-gap];
a[j] = x;
}
}
5、快速排序（最快）
建议用上面写法。
void quick_sort(int l, int r)
{
if (l >= r)
return ;
int x = a[l+r>>1], i = l-1, j = r+1;
while (i < j)
{
while (a[++ i] < x);
while (a[-- j] > x);
if (i < j)
swap(a[i], a[j]);
}
sort(l, j), sort(j+1, r);
}
6、归并排序
void merge_sort(int l, int r)
{
if (l >= r)
return;
int temp[N];
int mid = l+r>>1;
merge_sort(l, mid), merge_sort(mid+1, r);
int k = 0, i = l, j = mid+1;
while (i <= mid && j <= r)
{
if (a[i] < a[j])
temp[k ++ ] = a[i ++ ];
else
temp[k ++ ] = a[j ++ ];
}
while (i <= mid)
temp[k ++ ] = a[i ++ ];
while (j <= r)
temp[k ++ ] = a[j ++ ];
for (int i = l, j = 0; i <= r; i ++ , j ++ )
a[i] = temp[j];
}
7、堆排序
（须知此排序为使用了模拟堆，为了使最后一个非叶子节点的编号为n/2，数组编号从1开始）
void down(int u)
{
int t = u;
if (u<<1 <= n && h[u<<1] < h[t])
t = u<<1;
if ((u<<1|1) <= n && h[u<<1|1] < h[t])
t = u<<1|1;
if (u != t)
{
swap(h[u], h[t]);
down(t);
}
}
int main()
{
for (int i = 1; i <= n; i ++ )
cin >> h[i];
for (int i = n/2; i; i -- )
down(i);
while (true)
{
if (!n) break;
cout << h[1] << ' ';
h[1] = h[n];
n -- ;
down(1);
}
return 0;
}
8、基数排序
int maxbit()
{
int maxv = a[0];
for (int i = 1; i < n; i ++ )
if (maxv < a[i])
maxv = a[i];
int cnt = 1;
while (maxv >= 10)
maxv /= 10, cnt ++ ;
return cnt;
}
void radixsort()
{
int t = maxbit();
int radix = 1;
for (int i = 1; i <= t; i ++ )
{
for (int j = 0; j < 10; j ++ )
count[j] = 0;
for (int j = 0; j < n; j ++ )
{
int k = (a[j] / radix) % 10;
count[k] ++ ;
}
for (int j = 1; j < 10; j ++ )
count[j] += count[j-1];
for (int j = n-1; j >= 0; j -- )
{
int k = (a[j] / radix) % 10;
temp[count[k]-1] = a[j];
count[k] -- ;
}
for (int j = 0; j < n; j ++ )
a[j] = temp[j];
radix *= 10;
}
}
9、计数排序
void counting_sort()
{
int sorted[N];
int maxv = a[0];
for (int i = 1; i < n; i ++ )
if (maxv < a[i])
maxv = a[i];
int count[maxv+1];
for (int i = 0; i < n; i ++ )
count[a[i]] ++ ;
for (int i = 1; i <= maxv; i ++ )
count[i] += count[i-1];
for (int i = n-1; i >= 0; i -- )
{
sorted[count[a[i]]-1] = a[i];
count[a[i]] -- ;
}
for (int i = 0; i < n; i ++ )
a[i] = sorted[i];
}
10、桶排序
（基数排序是桶排序的特例，优势是可以处理浮点数和负数，劣势是还要配合别的排序函数）
vector<int> bucketSort(vector<int>& nums)
{
int n = nums.size();
int maxv = *max_element(nums.begin(), nums.end());
int minv = *min_element(nums.begin(), nums.end());
int bs = 1000;
int m = (maxv-minv)/bs+1;
vector<vector<int>> bucket(m);
for (int i = 0; i < n; ++i)
{
bucket[(nums[i]-minv)/bs].push_back(nums[i]);
}
int idx = 0;
for (int i = 0; i < m; ++i)
{
int sz = bucket[i].size();
bucket[i] = quickSort(bucket[i]);
for (int j = 0; j < sz; ++j)
{
nums[idx++] = bucket[i][j];
}
}
return nums;
}
兄弟有时间填个邀请码hhhhhhhhh（可以得AC币，邀请码在学生认证那填） 我的邀请码是：GUDFH
我认证了