九大经典排序算法

1.1 直接插入排序（Insertion Sort）

插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据在已排序序列中从前向后扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从前向后的扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
在所有的简单排序（算法性能为O(n^2)）中，直接插入排序的整体性能最好。

1.2 希尔排序(Shellsort)

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。

Shellsort, also known as Shell sort or Shell’s method, is an in-place comparison sort. It can be seen as either a generalization of sorting by exchange (bubble sort) or sorting by insertion (insertion sort). The method starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. Starting with far apart elements, it can move some out-of-place elements into position faster than a simple nearest neighbor exchange. Donald Shell published the first version of this sort in 1959. The running time of Shellsort is heavily dependent on the gap sequence it uses. For many practical variants, determining their time complexity remains an open problem.

稳定性：
由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。

1.3 冒泡排序

Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm, which is a comparison sort, is named for the way smaller or larger elements “bubble” to the top of the list. Although the algorithm is simple, it is too slow and impractical for most problems even when compared to insertion sort. It can be practical if the input is usually in sorted order but may occasionally have some out-of-order elements nearly in position.

1.4 快速排序(Quicksort)

快速排序采用分治策略，其难点在于如何取得轴点（Pivot Points），也就是如何分（divide）的问题。

Quicksort (sometimes called partition-exchange sort) is an efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order. Developed by Tony Hoare in 1959 and published in 1961, it is still a commonly used algorithm for sorting. When implemented well, it can be about two or three times faster than its main competitors, merge sort and heapsort.
Quicksort is a comparison sort, meaning that it can sort items of any type for which a “less-than” relation (formally, a total order) is defined. In efficient implementations it is not a stable sort, meaning that the relative order of equal sort items is not preserved. Quicksort can operate in-place on an array, requiring small additional amounts of memory to perform the sorting.

1.5 简单选择排序(Simple Selection Sort)

选择排序是一种简单直观的排序算法。算法特点:每经过一趟排序都能得到全局的最大（小）值。

1.6 堆排序(Heapsort)

堆排序（Heapsort）是一种高级的选择排序，是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

通常堆是通过一维数组来实现的。在数组起始位置为0的情形中：
父节点i的左子节点在位置(2i+1);
父节点i的右子节点在位置(2i+2);
子节点i的父节点在位置(i-1)/2;

相关历史：
Heapsort was invented by J. W. J. Williams in 1964. This was also the birth of the heap, presented already by Williams as a useful data structure in its own right. In the same year, R. W. Floyd published an improved version that could sort an array in-place, continuing his earlier research into the treesort algorithm.

1.7 归并排序(Merge Sort)

归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法，效率为O(n log n)。1945年由约翰·冯·诺伊曼(John von Neumann)首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。

1.8 计数排序(Counting Sort)

计数排序（Counting sort）是一种稳定的线性时间排序算法。计数排序使用一个额外的数组Cnt，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组Cnt来将A中的元素排到正确的位置。

Although radix sorting itself dates back far longer(1887), counting sort, and its application to radix sorting, were both invented by Harold H. Seward in 1954.

1.9 基数排序（Radix Sort）

基数排序（英语：Radix sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。基数排序的发明可以追溯到1887年赫尔曼·何乐礼(Herman Hollerith)在打孔卡片制表机（Tabulation Machine）上的贡献。
它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

// main.cpp 
//直接插入排序 希尔排序 冒泡排序（简单交换排序） 快速排序 简单选择排序 堆排序
//2路-归并排序 计数排序 基数排序 
 
 
#include <iostream>
#include <iomanip>
using namespace std;
#define N 10
 
 
void test_InsertSort_Straight(int* a, int n);
void test_InsertSort_Shell(int* a, int n);
void test_SwapSort_Bubble(int* a, int n);
void test_SwapSort_Quick(int* a, int n);
void test_SelectionSort_Simple(int* a, int n);
void test_SelectionSort_Heap(int* a, int n);
void test_MergeSort_2(int* a, int n);
void test_RadixSort_Count(int* a, int n);
void test_RadixSort_Radix(int* a, int n);
 
 
 
 
void test_InsertSort()
{
	int a[N] = {21, 26, 5, 96, 45, 12, 26, 14, 15, 12};
	cout << "原始数据如下" << endl;
	cout << "------------------------------------------" << endl;
	for(int i = 0; i < N; ++i)
	{
		cout << left << setw(4) << a[i];
	}
	cout << endl;
 
 
	//测试直接插入排序
	test_InsertSort_Straight(a, N);
	//测试希尔排序
	test_InsertSort_Shell(a, N);
}
 
 
void test_SelectionSort()
{
	int a[N] = {21, 26, 5, 96, 45, 12, 26, 14, 15, 12};
	cout << "原始数据如下" << endl;
	cout << "------------------------------------------" << endl;
	for(int i = 0; i < N; ++i)
	{
		cout << left << setw(4) << a[i];
	}
	cout << endl;
 
 
	//测试简单选择排序
	test_SelectionSort_Simple(a, N);
	//测试堆排序
	test_SelectionSort_Heap(a, N);
}
 
 
void test_SwapSort()
{
	int a[N] = {21, 26, 5, 96, 45, 12, 26, 14, 15, 12};
	cout << "原始数据如下" << endl;
	cout << "------------------------------------------" << endl;
	for(int i = 0; i < N; ++i)
	{
		cout << left << setw(4) << a[i];
	}
	cout << endl;
	////测试冒泡排序
	test_SwapSort_Bubble(a, N);
	//测试快速排序
	test_SwapSort_Quick(a, N);
}
 
 
void test_MergeSort()
{
	int a[N] = {21, 26, 5, 96, 45, 12, 26, 14, 15, 12};
	cout << "原始数据如下" << endl;
	cout << "------------------------------------------" << endl;
	for(int i = 0; i < N; ++i)
	{
		cout << left << setw(4) << a[i];
	}
	cout << endl;
	//2路-归并排序
	test_MergeSort_2(a, N);
}
 
 
void test_RadixSort()
{
	int a[N] = {21, 26, 5, 96, 45, 12, 26, 14, 15, 12};
	cout << "原始数据如下" << endl;
	cout << "------------------------------------------" << endl;
	for(int i = 0; i < N; ++i)
	{
		cout << left << setw(4) << a[i];
	}
	cout << endl;
	//计数排序
	test_RadixSort_Count(a, N);
	//基数排序
	test_RadixSort_Radix(a, N);
}
 
 
int main()
{
	//所有的排序目的都是排出由小到大的顺序
	//test_InsertSort();
	//test_SwapSort();
	//test_SelectionSort();
	//test_MergeSort();
	test_RadixSort();
	return 0;
}

//01InsertSort.cpp
#include <iostream>
#include <iomanip>
using namespace std;

static void print(int* a, int n)
{
    for(int i = 0; i < n; ++i)
    {
        cout << left << setw(4) <<a[i];
    }
    cout << endl;
}

void test_InsertSort_Straight(int* a, int n)
{
    //对比shell排序，这里st=0；step=1；
    for(int i = 0 + 1; i < n; ++i)
    {
        //存储当前待比较的变量
        int tem = a[i];
        int j = i;
        for(; 1 <= j && tem < a[j - 1]; --j)
        {
            //元素后移
            a[j] = a[j - 1];
        }
        a[j] = tem;
    }
    cout << "直接插入排序之后的结果如下：" << endl;
    print(a, n);
    cout << endl;
}


//对数组a作一趟希尔插入排序。本算法和一趟直接插入排序相比，做了一下修改：
//   1.前后记录位置的增量为step，而不是1
static void ShellInsert(int* a, int n, int step)
{
    for(int st = 0; st < step; ++st)
    {
        //这边就是直接插入排序
        for(int i = st + step; i < n; i += step)
        {
            int tem = a[i];
            int j = i;
            for(; step <= j && tem < a[j - step]; j -= step)
            {
                //元素后移
                a[j] = a[j - step]
            }
            a[j] = tem;
        }
    }
    /*cout << "步长为" << step << ", 希尔排序之后的结果如下：" << endl;
	print(a, n);
	cout << endl;*/
}
 void test_InsertSort_Shell(int* a, int n)
 {
     //stepInc位置的增量
	for(int stepInc = n >> 1; 1 <= stepInc; stepInc >>= 1)
	{
		ShellInsert(a, n, stepInc);
	}
	cout << "希尔排序之后的结果如下：" << endl;
	print(a, n);
	cout << endl;
 }
 //WARNING:  点评：自己写的简单插入排序，用到了swap。其实免去这个操作。做到真正的只插入。
void Mytest_InsertSort_Straight(int* a, int n)
{
 
 
	for(int i = 1; i < n; ++i)
	{
		for(int j = i; 0 < j; --j)
		{
			if(a[j] < a[j - 1])
			{
				//如果a[j-1]大于a[j]的时候，对换二者
				swap(a[j], a[j - 1]);
			}
			else
			{
				//说明数组a[0,..,j]部分已经排序成功，直接跳出循环
				break;
			}
		}
	}
	cout << "直接插入排序之后的结果如下：" << endl;
	print(a, n);
	cout << endl;
}

// 02SwapSort.cpp
#include <iostream>
#include <iomanip>
using namespace std;
 
 
static void swap(int& a, int& b)
{
	int tem = a;
	a = b;
	b = tem;
}
 
 
static void print(int* a, int n)
{
	for(int i = 0; i < n; ++i)
	{
		cout << left << setw(4) << a[i];
	}
	cout << endl;
}
 
 
void test_SwapSort_Bubble(int* a, int n)
{
	for(int i = 0; i < n - 1; ++i)
	{
		bool isSorted = true;
		for(int j = 0; j < n - i - 1; ++j)
		{
			if(a[j + 1] < a[j])
			{
				swap(a[j], a[j + 1]);
				isSorted = false;
			}
		}
		if(true == isSorted)
		{
			break;
		}
	}
	cout << "冒泡排序之后的结果如下：" << endl;
	print(a, n);
	cout << endl;
}
 
 
//点评：没有考虑提前退出的情况
void Mytest_SwapSort_Bubble(int* a, int n)
{
	for(int i = 0; i < n -1; ++i)
	{
		for(int j = 0; j < n - i - 1; ++j)
		{
			if(a[j + 1] < a[j])
			{
				swap(a[j], a[j + 1]);
			}
		}
	}
	cout << "冒泡排序之后的结果如下：" << endl;
	print(a, n);
	cout << endl;
}
 
 
static int getMiddleID(int* a, int st, int mid, int ed)
{
	int res;
	if(a[st] < a[mid])
	{
		if(a[mid] < a[ed])
		{
			res = mid;
		}
		else
		{
			res = a[st] < a[ed] ? ed : st;
		}
	}
	else
	{
		if(a[ed] < a[mid])
		{
			res = mid;
		}
		else
		{
			res = a[st] > a[ed] ? ed : st;
		}
	}
	return res;
}
 
 
//获取轴点的位置，此时轴点之前的记录均不大于轴点的值，轴点之后的记录均小于轴点的值
static int Partition(int* a, int st, int ed)
{
	/*int stPos = getMiddleID(a, st, (ed - st) / 2, ed);
	swap(a[st], a[stPos]);*/
	int tem = a[st];
	while(st < ed)
	{
		//ERROR:这两次while当中，至少要出现一次等于<=,否则对于相等元素，会陷入无限循环中；
		//轴点之后的记录均小于轴点的值
		while(st < ed&&tem < a[ed])
		{
			--ed;
		}
		a[st] = a[ed];
		//轴点之前的记录均不大于轴点的值
		while(st < ed&&a[st] <= tem)
		{
			++st;
		}
		a[ed] = a[st];
	}
	a[st] = tem;
	return st;
}
 
 
//快速排序算法
static void QuickSort(int* a, int st, int ed)
{
	if(st < ed)
	{
		//pivot 轴点
		int pivotLoc = Partition(a, st, ed);
		QuickSort(a, st, pivotLoc - 1);
		QuickSort(a, pivotLoc + 1, ed);
	}
}
 
 
void test_SwapSort_Quick(int* a, int n)
{
	//对于初始点的选择，从数组元素的起点，中点和终点三者当中，选择中间大的数作为起点。
	//int stPos = getMiddleID(a, n, 0, (n - 1) / 2, n - 1);
	QuickSort(a, 0, n - 1);
	cout << "快速排序之后的结果如下：" << endl;
	print(a, n);
	cout << endl;
}

// 03SelectionSort.cpp
#include <iostream>
#include <iomanip>
using namespace std;
 
 
static void swap(int& a, int& b)
{
	int tem = a;
	a = b;
	b = tem;
}
 
 
static void print(int* a, int n)
{
	for(int i = 0; i < n; ++i)
	{
		cout << left << setw(4) << a[i];
	}
	cout << endl;
}
 
 
void test_SelectionSort_Simple(int* a, int n)
{
	for(int i = 0; i < n; ++i)
	{
		int minIdx = i;
		for(int j = i + 1; j < n; ++j)
		{
			if(a[j] < a[minIdx])
			{
				minIdx = j;
			}
		}
		if(i != minIdx)
		{
			swap(a[i], a[minIdx]);
		}
	}
	cout << "简单选择排序之后的结果如下：" << endl;
	print(a, n);
	cout << endl;
}
 
 
//n表示数组的长度， adjPos表示需要调整的堆的位置；
//堆的调整都是默认顶点下面的子树都已经是大根堆
static void HeapAdjust(int* a, int n, int adjPos)
{
	int adjVal = a[adjPos];
	//ERROR:i = 2*i +1代表的意思就是i指向其左孩子   注意不是i= 2*i
	for(int i = 2 * adjPos + 1; i < n; i = 2*i +1)
	{
		//如果存在右孩子的话，比较二者，取其中较大者的位序
		if(i < n - 1 && a[i] < a[i + 1])
		{
			++i;
		}
		//如果孩子结点的最大值都小于adjVal，则调整提前结束
		if(a[i] < adjVal)
		{
			break;
		}
		//依次将元素往上移
		a[adjPos] = a[i];
		adjPos = i;
	}
	a[adjPos] = adjVal;
}
 
 
//建立大根堆，以便从小到大进行排序
static void createMaxHeap(int* a, int n)
{
	for(int i = (n - 2) / 2; 0 <= i; --i)
	{
		HeapAdjust(a, n, i);
	}
}
 
 
void test_SelectionSort_Heap(int* a, int n)
{
	//建立大根堆
	createMaxHeap(a, n);
	//依次将顶元素和最后一个元素进行交换，逐渐排序
	for(int i = n - 1; 0 <= i; --i)
	{
		swap(a[0], a[i]);
		HeapAdjust(a, i, 0);
	}
 
 
	cout << "堆排序之后的结果如下：" << endl;
	print(a, n);
	cout << endl;
}

// 04MergeSort.cpp
#include <iostream>
#include <iomanip>
using namespace std;
 
 
static void print(int* a, int n)
{
	for(int i = 0; i < n; ++i)
	{
		cout << left << setw(4) << a[i];
	}
	cout << endl;
}
 
 
static void merge(int* a, int st, int mid, int ed)
{
	int* b = new int[mid - st + 1];
	//ERROR：对于b[]复制存在错误，不是每次从a[0]开始复制，而是从st开始复制
	/*for(int i = 0; i <= mid; ++i)
	{
	b[i] = a[i];
	}*/
	for(int i = 0; i < mid - st + 1; ++i)
	{
		b[i] = a[i + st];
	}
	//ERROR:这里int k = st;注意不是k = 0
	int k = st;
	for(int i = st, j = mid + 1; i <= mid || j <= ed;)
	{
		//注意b[i - st] <= a[j]此处，必须与下面的a[j] < b[i - st]，构成封闭的集合
		//ERROR：未能考虑等于号
		if((i <= mid&&j <= ed&&b[i - st] <= a[j]) || ed < j)
		{
			a[k++] = b[i - st];
			++i;
		}
		else if(i <= mid&&j <= ed && a[j] < b[i - st])
		{
			a[k++] = a[j];
			++j;
		}
		else
		{
			break;
		}
	}
	delete[] b;
}
 
 
static void  mergeSort(int* a, int st, int ed)
{
	if(st < ed)
	{
		int mid = st + (ed - st) / 2;
		mergeSort(a, st, mid);
		mergeSort(a, mid + 1, ed);
		merge(a, st, mid, ed);
	}
}
 
 
void test_MergeSort_2(int* a, int n)
{
	mergeSort(a, 0, n - 1);
	cout << "归并排序之后的结果如下：" << endl;
	print(a, n);
	cout << endl;
}

// 05RadixSort.cpp
#include <iostream>
#include <iomanip>
#include <cstring>
#include <cmath>
using namespace std;
 
 
static void print(int* a, int n)
{
	for(int i = 0; i < n; ++i)
	{
		cout << left << setw(4) << a[i];
	}
	cout << endl;
}
 
 
//假设数组元素在0~99之间，进行取值
//计数排序
void test_RadixSort_Count(int* a, int n)
{
	//计数数组
	int* cnt = new int[100];
	memset(cnt, 0, sizeof(int) * 100);
	
	//此时，cnt[a[i]]表示值为a[i]的元素在数组a当中出现的次数
	//WARNING: 注意这里i < n,不是i < 100
	for(int i = 0; i < n; ++i)
	{
		++cnt[a[i]];
	}
	//此时，cnt[i] - 1表示值为i的元素在数组a中排序之后的最大可能位置
	//ERROR: 注意这里i < 100,不是i < n
	for(int i = 1; i < 100; ++i)
	{
		cnt[i] += cnt[i - 1];
	}
	//tmp[]临时数组，将数组a复制到数组tmp中去
	int* tmp = new int[n];
	for(int i = 0; i < n; ++i)
	{
		tmp[i] = a[i];
	}
	////ERROR:计数排序,这样虽然也能得到正确结果，但是不能保证排序的稳定性
	//for(int i = 0; i < n; ++i)
	//{
	//	a[--cnt[tmp[i]]] = tmp[i];
	//}
 
 
	//稳定版：计数排序
	for(int i = n-1; 0 <= i; --i)
	{
		a[--cnt[tmp[i]]] = tmp[i];
	}
 
 
	cout << "计数排序之后的结果如下：" << endl;
	print(a, n);
	cout << endl;
	delete[] cnt;
	delete[] tmp;
}
 
 
static int getRadix(int num, int sq, int RADIX)
{
	return (num / (int)pow(RADIX, sq)) % RADIX;
}
 
 
static void Distribute(int* a, int n, int sq, int* cnt, int* tmp, int RADIX)
{
	memset(cnt, 0, sizeof(int)*RADIX);
	for(int i = 0; i < n; ++i)
	{
		int ord = getRadix(a[i], sq, RADIX);
		++cnt[ord];
	}
}
 
 
static void Collect(int* a, int n, int sq, int* cnt, int* tmp, int RADIX)
{
	for(int i = 1; i < RADIX; ++i)
	{
		cnt[i] += cnt[i - 1];
	}
	for(int i = 0; i < n; ++i)
	{
		tmp[i] = a[i];
	}
	for(int i = n - 1; 0 <= i; --i)
	{
		int ord = getRadix(tmp[i], sq, RADIX);
		a[--cnt[ord]] = tmp[i];
	}
}
 
 
void test_RadixSort_Radix(int* a, int n)
{
	int keyNum = 2;
	int RADIX = 10;
	int* cnt = new int[RADIX];
	int* tmp = new int[n];
 
 
	for(int i = 0; i < keyNum; ++i)
	{
		Distribute(a, n, i, cnt, tmp, RADIX);
		Collect(a, n, i, cnt, tmp, RADIX);
		cout << i + 1 << "次基数排序之后的结果如下：" << endl;
		print(a, n);
		cout << endl;
	}
	cout << "基数排序之后的结果如下：" << endl;
	print(a, n);
	cout << endl;
	delete[] cnt;
	delete[] tmp;
}