考研数据结构——每日一题[快速排序]

785. 快速排序

给定你一个长度为 n 的整数数列。

请你使用快速排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式 输入共两行，第一行包含整数 n。

第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整个数列。

输出格式 输出共一行，包含 n 个整数，表示排好序的数列。

数据范围 1≤n≤100000 输入样例： 5 3 1 2 4 5 输出样例： 1 2 3 4 5

记讲义的复杂度[最优，平均，最差]（不需要会推导）

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1000010; //开越大桶排序过越多样例

int n;
int q[N];

void insert_sort()  //直接插入排序  [一个一个插入，插入到前面，要把数组整体后移] 
{
	for(int i = 1;i < n; i++)//把每个数插入到排序位置上 
	{//q[i]存t   【形象类比： 斗地主整理牌】 
		int t = q[i] , j = i;//加入新的元素q[i]，遍历前i个元素,把q[i]排序到对应位置上 
		while(j && q[j - 1] > t)  //j从i开始从已经确定的尾部开始往前遍历: 所以第一个用j- 1， 找到第一个 
		{
			q[j] = q[j - 1];
			j --;	
		} 
		q[j] = t;	
	}	
}
int main()
{
	for(int i = 0;i < 10 ;i ++) scanf("%d ",&q[i]);
	//merge_sort(q,0,9); 
	insert_sort();
	
	for(int i = 0;i < 10 ;i ++) printf("%d ",q[i]);
	
	return 0;
}