实验5  快速排序算法

一、实验目的

1. 熟悉在数组上进行各种排序的方法和算法

2. 掌握在数组上进行一趟快速排序的思路

3. 掌握快速排序的时间复杂度和要求的数据特性

二、实验内容

1. 设计快速排序算法

2. 对无序的数据进行快速排序，并分析其性能

三、实验数据输入输出要求

输入示例：

10

26  7  3  18  21  6  28  157  16  53

(说明：第一行数据10表示共有10个整数数据要排序）

输出示例：

3  6  7  16  18  21  26  28  53  157

四、程序代码

#include<iostream>
using namespace std;

void QuickSort(int* arr, int left, int right)
{
	if (left > right)
	{
		return;
	}
	int i = left;
	int j = right;
	int flag = arr[left];
	while (i != j)
	{
		while (arr[j] > flag && i < j)
		{
			j--;
		}
		while (arr[i] <= flag && i < j)
		{
			i++;
		}
		int temp = 0;
		if (i < j)
		{
			temp = arr[j];
			arr[j] = arr[i];
			arr[i] = temp;
		}
	}
	arr[left] = arr[i];
	arr[i] = flag;
	QuickSort(arr, left, i - 1);
	QuickSort(arr, i + 1, right);
}
int main()
{
	int length;
	scanf_s("%d", &length);
	int array[10];
	int i;
	for (i=0;i< length;i=i+1)
		scanf_s("%d", array+i);
	array[i+1] = '\0';
	QuickSort(array, 0, 9);
	for (auto e : array)
	{
		cout << e << " ";
	}
	cout << endl;
	return 0;
}