- 直接插入
- 折半插入
- 希尔排序
- 快排
- 双向冒泡
- 简单选择排序
- 归并排序
- 堆排序
希尔排序出人意料，利用随机枢值的快速排序才能发挥其“名不虚传”的优势，2路归并排序表现出众
给定N个（长整型范围内的）整数，要求输出从小到大排序后的结果。
本题旨在测试各种不同的排序算法在各种数据情况下的表现。各组测试数据特点如下：
数据1：只有1个元素；
数据2：11个不相同的整数，测试基本正确性；
数据3：10^3个随机整数；
数据4：10^4个随机整数；
数据5：10^5个随机整数；
数据6：10^5个顺序整数；
数据7：10^5个逆序整数；
数据8：10^5个基本有序的整数；
数据9：10^5个随机正整数，每个数字不超过1000。
输入格式:
输入第一行给出正整数N，随后一行给出N个（长整型范围内的）整数，其间以空格分隔。
输出格式:
在一行中输出从小到大排序后的结果，数字间以1个空格分隔，行末不得有多余空格。
直接插入
InsertSort2.png
折半插入
InsertSortHalf2.png
快排，随机枢值
QuickSortByRandom2.png
快排，第一项作为枢值
QuisckSort2.png
希尔排序
ShellSort2.png
双向冒泡
BubbleSort2.png
简单选择排序
SimpleSelect2.png
2路归并
MergeSort2.png
//
// Created by xcp on 18-11-1.
//
// Sort.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <iostream>
typedef int ElemType;
//---------------QuickSort----------------------
int Partition(ElemType a[], int l, int h) {
//随机取枢值
int ri = l + rand() % (h - l + 1);
std::swap(a[l], a[ri]);
int p = a[l];
while (l < h) {
while (l < h&&a[h] >= p) {
--h;
}
a[l] = a[h];
while (l < h&&a[l] <= p) {
++l;
}
a[h] = a[l];
}
a[l] = p;
return l;
}
void QuickSort(ElemType a[], int l, int h) {
if (l < h) {
int p = Partition(a, l, h);
QuickSort(a, l, p - 1);
QuickSort(a, p + 1, h);
}
}
//-----------------InsertSort----------------
//a[0] not use
void InsterSort(ElemType a[], int n) {
int j;
for (int i = 2; i <= n; ++i) {
if (a[i] < a[i - 1]) {
a[0] = a[i];
for (j = i - 1; a[j] > a[0]; --j) {
a[j + 1] = a[j];
}
a[j + 1] = a[0];
}
}
}
//a[0] not use
void InsterSortHalf(ElemType a[], int n) {
int low, hight, mid;
for (int i = 2; i <= n; ++i) {
if (a[i] < a[i - 1]) {
a[0] = a[i];
low = 1; hight = i - 1;
while (low <= hight) {
mid = (low + hight) / 2;
if (a[mid] > a[0]) {
hight = mid - 1;
}
else
low = mid + 1;
}
low = i - 1;
while (low > hight) {
a[low + 1] = a[low];
--low;
}
a[hight + 1] = a[0];
}
}
}
//--------------------ShellSort--------------------
//a[0] not use
void ShellInsertSort(ElemType a[], int n, int span) {
for (int i = n / span; i >= 1; i = i / span) {
for (int j = 1 + i; j <= n; ++j) {
if (a[j] < a[j - i]) {
a[0] = a[j];
int k;
for (k = j - i; k > 0 && a[k] > a[0]; k -= i) {
a[k + i] = a[k];
}
a[k + i] = a[0];
}
}
}
}
//----------------BubbeSort-------------------
void BubbleSort(ElemType a[], int n) {
int l = 1, h = n;
bool flag = true;
while (l < h&&flag) {
flag = false;
for (int i = l; i < h; ++i) {
if (a[i] > a[i + 1]) {
std::swap(a[i], a[i + 1]);
flag = true;
}
}
--h;
for (int j = h; j > l; --j) {
if (a[j] < a[j - 1]) {
std::swap(a[j], a[j - 1]);
flag = true;
}
}
++l;
}
}
//------------------SimpleSelect------------------
void SimpleSelect(ElemType a[], int n) {
int min;
//a[0] not use
for (int i = 1; i < n; ++i) {
min = i;
for (int j = i + 1; j <= n; ++j) {
if (a[j] < a[min]) {
min = j;
}
}
if (i != min)
std::swap(a[min], a[i]);
}
}
//--------------MergeSort-----------------------
int b[100001];
void Merge(ElemType a[], int l, int h, int mid) {
for (int i = l; i <= h; ++i) {
b[i] = a[i];
}
int p, q, k;
for (p = l, q = mid + 1, k = l; p <= mid && q <= h; ++k) {
if (b[p] > b[q]) {
a[k] = b[q++];
}
else {
a[k] = b[p++];
}
}
while (p <= mid) {
a[k++] = b[p++];
}
while (q <= h) {
a[k++] = b[q++];
}
}
void MergeSort(ElemType a[], int l, int h) {
if (l < h) {
int mid = (l + h) / 2;
MergeSort(a, l, mid);
MergeSort(a, mid + 1, h);
Merge(a, l, h, mid);
}
}
//--------------HeapSort-----------------------
//大顶堆
void adjustHeap(int a[], int i, int n) { //调整i及其子树
int p = a[i]; //暂存
for (int k = i * 2+1; k < n; k = k * 2+1) //i的左子树或其子节点的左子树
{
if (k+1 < n&&a[k] < a[k + 1]) {
k++; //k指向子节点中大的那个
}
if (a[k] > p) { //若子节点中大的那个大于父节点
a[i] = a[k]; //将该节点赋值给父节点(父节点已暂存)
i = k; //用i指向父节点该存放的位置
//由于当前节点会被父节点替换，所以需要对其子节点再进行调整->继续for循环
}
else
{
break;//如果子节点都不大于父节点，不用调整(因为下面已经是堆)
}
}
a[i] = p; //将父节点放到最终的位置(父节点及其子树全部是堆)
}
void HeapSort(int a[], int n) {
for (int i = n / 2-1; i >= 0; i--) //从最下非叶节点开始
{
adjustHeap(a, i, n);
}
//到这里a已经是大顶堆
//a[0]是a[0~n-1]的最大值，将其置换到a[n-1],a[n-1]有序
//调整a[0~n-2]为小顶堆,再将次大值a[0]置换到a[n-2],(a[n-2]~a[n-1])有序
//...最终得到递增序列a[0]~a[n-1]
for (int i = n-1; i > 0; i--)
{
std::swap(a[0], a[i]);
adjustHeap(a, 0, i);
}
}
int main() {
int n= 1000;
int a[100001];
std::cin >> n;
//堆排需要a[0]
for (int i = 0; i < n; i++)
{
std::cin >> a[i];
}
HeapSort(a, n);
std::cout << a[0];
for (int j = 1; j < n; ++j) {
std::cout << " " << a[j];
}
//下列排序方式均不使用a[0]
/*
for (int i = 1; i <= n; ++i) {
std::cin >> a[i];
}*/
//InsterSort(a,n);
//ShellInsertSort(a,n,2);
//InsterSortHalf(a,n);
//QuickSort(a,1,n);
//SimpleSelect(a,n);
//BubbleSort(a,n);
//MergeSort(a, 1, n);
/*
std::cout << a[1];
for (int j = 2; j <= n; ++j) {
std::cout << " " << a[j];
}*/
return 0;
}
