一种是取前中后三个居中的元素放在最前面（自己写得），一种是直接取数组最中间元素做基准（网上扒的）。求大佬指教，另外好像第四个点是全部一样的数字。 第一种方法

#include <iostream>
#include <stdio.h>
inline void swap(long long& a, long long& b) {
	long long cup = 0;
	cup = a;
	a = b;
	b = cup;
}
inline void change(long long* shu, int low, int high) {
	long long mid = 0;
	long long* tosort = new long long[3];
	tosort[0] = low;
	tosort[1] = (low + high) / 2;
	tosort[2] = high;
	for (int i = 1; i < 3; i++) {//对首元素末元素中间元素插入排序
		int j = i - 1;
		while (j > -1 && shu[tosort[j]] > shu[tosort[j+1]]) {
			swap(tosort[j + 1], tosort[j]);
			j--;
		}
	}
	mid = tosort[1];//取居中元素下标
	swap(shu[mid], shu[low]);//与首元素交换
}
void insertsort(long long* shu,int low,int high) {//插入排序
	for (int i = low + 1; i < high + 1; i++) {
		int j = i - 1;
		while (j > low - 1 && shu[j] > shu[j+1]) {
			swap(shu[j], shu[j+1]);
			j--;
		}
	}
}
void qsort(long long* shu, int low, int high) {
	if (low >= high) {
		return;
	}
	int pivot = low;
	int l = low;
	int r = high+1;
	change(shu, low, high);
	do{
		while (shu[--r] > shu[pivot]) ;//先动再比(重点)
		while (l<high+1&&shu[++l] < shu[pivot]) ;//手动防止越界(重点)
		if (l < r) {
			swap(shu[l], shu[r]);
		}
	}while(l < r);
	swap(shu[r], shu[pivot]);
	if (r + 1 - low < 10 && r + 1 - low>0) insertsort(shu, low, r - 1);//元素数在2和10之间使用插入排序
	else qsort(shu, low, r - 1);
	if (high - r - 1 < 10 && high - r - 1 > 0) insertsort(shu, r + 1, high);
	else qsort(shu, r + 1, high);
}
int main() {
	int N = 0;
	scanf_s("%d", &N);
	long long* shu = new long long[N];
	for (int i = 0; i < N; i++) {
		scanf_s("%lld", &shu[i]);
	}
	if (N > 0) {
		qsort(shu, 0, N - 1);
	}
	for (int i = 0; i < N; i++) {
		printf("%lld", shu[i]);
		if (i < N + 1) {
			printf(" ");
		}
	}
}

第二种方法 十几毫秒

#include<iostream>
#include<cstdio>

using namespace std;
const int N = 1e5 + 10;

int q[N];
int n;

void quick_sort(int q[], int l, int r)
{
	if(l >= r)	return;
	int x = q[l + r >> 1], i = l - 1, j = r + 1;
	while(i < j)
	{
		while(q[++i] < x);
		while(q[--j] > x);
		if(i < j)	swap(q[i], q[j]);
	}
	quick_sort(q, l, j);
	quick_sort(q, j + 1, r);
}

int main()
{
	scanf("%d", &n);
	for(int i = 0; i < n; ++i)  scanf("%d", &q[i]);

	quick_sort(q, 0, n - 1);

	for(int i = 0; i < n; ++i)  printf("%d ", q[i]);

	return 0;
}