0 算法概述
所谓排序算法，即通过特定的算法因式将一组或多组数据按照既定模式进行重新排序。排序算法是《数据结构与算法》中最基本的算法之一。
0.1 术语解释
1、稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 仍然在 b 的前面，则为稳定排序。
2、非稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 可能不在 b 的前面，则为非稳定排序。
3、原地排序：原地排序就是指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序。
4、非原地排序：需要利用额外的数组来辅助排序。
5、时间复杂度：一个算法执行所消耗的时间，对排序数据的总的操作次数。
6、空间复杂度：运行完一个算法所需的内存大小，是指算法在计算机内执行时所需存储空间的度量。
7、In-place：占用常数内存，不占用额外内存。
8、Out-place：占用额外内存。
0.2 算法的分类
十种常见排序算法可以分为两大类：
比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
0.3 算法的复杂度
排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括：
关于时间复杂度：
1、平方阶 (O(n2）) 排序 各类简单排序：直接插入、直接选择和冒泡排序。
2、线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序。
3、O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。希尔排序。
4、线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。
关于稳定性：
稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。
不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。
1 冒泡排序
冒泡排序（Bubble Sort）是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
1.1 算法描述
① 比较相邻的元素。如果前者比后者大，就交换它们两个；
② 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
③ 针对所有的元素重复以上的步骤，除了最后一个；
④ 重复步骤①~③，直到排序完成。
1.2 动图演示
1.3 算法分析
什么时候最快？
当输入的数据已经是正序时（都已经是正序了，我还要你冒泡排序有何用啊），此时时间复杂度O(n） 。
什么时候最慢？
当输入的数据是反序时（写一个 for 循环反序输出数据不就行了，干嘛要用你冒泡排序呢，我是闲的吗），此时时间复杂度O(n2）。
1.4 代码实现
1、Python语言实现
def bubbleSort(arr):
for i in range(1, len(arr)):
for j in range(0, len(arr)-i):
if arr[j] > arr[j+1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr2、C++语言实现
/* 冒泡排序 */
void BubbleSort(int arr[], int length)
// arr： 需要排序的数组； length： 数组长度 注： int cnt = sizeof(a) / sizeof(a[0]);获取数组长度
{
for (int i = 0; i < length; i++)
{
for (int j = 0; j < length - i - 1; j++)
{
if (arr[j] > arr[j + 1])
{
int temp;
temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
}
}3、java语言实现
public class BubbleSort {
public static int[] bubbleSort(int[] arr) {
if (arr == null || arr.length < 2) {
return arr;
}
int n = arr.length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n -i - 1; j++) {
if (arr[j + 1] < arr[j]) {
int t = arr[j];
arr[j] = arr[j+1];
arr[j+1] = t;
}
}
}
return arr;
}
}2 选择排序
选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
2.1 算法描述
① 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；
② 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾；
③ 重复步骤②，直到所有元素均排序完毕。
2.2 动图演示
2.3 算法分析
理想和非理想情况下，该排序算法的时间复杂度都是O(n2）。表现最稳定的排序算法之一，因为无论什么数据进去都是O(n2)的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧。
2.4 代码实现
1、Python语言实现
def selectionSort(arr):
for i in range(len(arr) - 1):
# 记录最小数的索引
minIndex = i
for j in range(i + 1, len(arr)):
if arr[j] < arr[minIndex]:
minIndex = j
# i 不是最小数时，将 i 和最小数进行交换
if i != minIndex:
arr[i], arr[minIndex] = arr[minIndex], arr[i]
return arr2、C++语言实现
// 自定义方法：交换两个变量的值
void swap(int *a,int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
/* 选择排序 */
void selection_sort(int arr[], int len)
{
int i,j;
for (i = 0 ; i < len - 1 ; i++) {
int min = i;
for (j = i + 1; j < len; j++) { // 遍历未排序的元素
if (arr[j] < arr[min]) { // 找到目前最小值
min = j; // 记录最小值
}
}
swap(&arr[min], &arr[i]); //做交换
/*if (index != i) // 不用自定义函数时可以用选择下面方式进行交换
{
temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
}*/
}
}
3、Java语言实现
public class SelectSort {
public static int[] selectSort(int[] a) {
int n = a.length;
for (int i = 0; i < n - 1; i++) {
int min = i;
for (int j = i + 1; j < n; j++) {
if(a[min] > a[j]) min = j;
}
//交换
int temp = a[i];
a[i] = a[min];
a[min] = temp;
}
return a;
}
}3 插入排序
插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
3.1 算法描述
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
① 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
② 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
3.2 动图演示
3.3 算法分析
插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
什么时候最快？
当输入的数据已经是正序时，此时时间复杂度O(n） 。
什么时候最慢？
当输入的数据是反序时，此时时间复杂度O(n2）。
3.4 代码实现
1、Python语言实现
def insertionSort(arr):
for i in range(len(arr)):
preIndex = i-1
current = arr[i]
while preIndex >= 0 and arr[preIndex] > current:
arr[preIndex+1] = arr[preIndex]
preIndex-=1
arr[preIndex+1] = current
return arr2、C++语言实现
/* 插入排序 */
void insertion_sort(int arr[], int len){
int i,j,key;
for (i=1;i<len;i++){
key = arr[i];
j=i-1;
while((j>=0) && (arr[j]>key)) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
}3、Java语言实现
public class InsertSort {
public static int[] insertSort(int[] arr) {
if(arr == null || arr.length < 2)
return arr;
int n = arr.length;
for (int i = 1; i < n; i++) {
int temp = arr[i];
int k = i - 1;
while(k >= 0 && arr[k] > temp)
k--;
//腾出位置插进去,要插的位置是 k + 1;
for(int j = i ; j > k + 1; j--)
arr[j] = arr[j-1];
//插进去
arr[k+1] = temp;
}
return arr;
}
}4 希尔排序
希尔排序（Shell Sort），也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。希尔排序是基于插入排序的以下两点性质而提出改进方法的：
- 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
- 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；
希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
希尔排序可以说是插入排序的一种变种。无论是插入排序还是冒泡排序，如果数组的最大值刚好是在第一位，要将它挪到正确的位置就需要 n – 1 次移动。也就是说，原数组的一个元素如果距离它正确的位置很远的话，则需要与相邻元素交换很多次才能到达正确的位置，这样是相对比较花时间了。
希尔排序就是为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序。
希尔排序的思想是采用插入排序的方法，先让数组中任意间隔为 h 的元素有序，刚开始 h 的大小可以是 h = n / 2,接着让 h = n / 4，让 h 一直缩小，当 h = 1 时，也就是此时数组中任意间隔为1的元素有序，此时的数组就是有序的了。
4.1 算法描述
① 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
② 按增量序列个数 k，对序列进行 k 趟排序；
③ 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
4.2 动图演示
4.3 算法分析
希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列，比较流行的间隔序列设置为：gap=length/2或gap=length/3+1。希尔排序的时间复杂度是：O(n1.3）~ O(n2）。
什么时候最快？
当输入的数据已经是正序时，此时时间复杂度O(n1.3） 。
什么时候最慢？
当输入的数据是反序时，此时时间复杂度O(n2）。
4.4 代码实现
1、Python语言实现
def shellSort(arr):
import math
gap=1
while(gap < len(arr)/3):
gap = gap*3+1
while gap > 0:
for i in range(gap,len(arr)):
temp = arr[i]
j = i-gap
while j >=0 and arr[j] > temp:
arr[j+gap]=arr[j]
j-=gap
arr[j+gap] = temp
gap = math.floor(gap/3)
return arr2、C++语言实现
void shellsSort(int arr[], int len) {
int d, i, j, temp;
for (d = len / 2; d >= 1; d /= 2) {
// 这里类似直接插入排序
for (i = d; i < len; i++) {
temp = arr[i];
for (j = i - d; j >= 0 && temp < arr[j]; j -= d) {
arr[j + d] = arr[j];
}
arr[j + d] = temp;
}
}
}3、Java语言实现
public class ShellSort {
public static int[] shellSort(int arr[]) {
if (arr == null || arr.length < 2) return arr;
int n = arr.length;
// 对每组间隔为 h的分组进行排序，刚开始 h = n / 2;
for (int h = n / 2; h > 0; h /= 2) {
//对各个局部分组进行插入排序
for (int i = h; i < n; i++) {
// 将arr[i] 插入到所在分组的正确位置上
insertI(arr, h, i);
}
}
return arr;
}
/**
* 将arr[i]插入到所在分组的正确位置上
* arr[i]] 所在的分组为 ... arr[i-2*h],arr[i-h], arr[i+h] ...
*/
private static void insertI(int[] arr, int h, int i) {
int temp = arr[i];
int k;
for (k = i - h; k > 0 && temp < arr[k]; k -= h) {
arr[k + h] = arr[k];
}
arr[k + h] = temp;
}
}5 归并排序
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法： 自上而下的递归及 自下而上的迭代。
5.1 算法描述
① 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
② 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
③ 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
④ 重复步骤 ③ 直到某一指针达到序列尾；
⑤ 将另一序列剩下的所有元素直接复制到合并序列尾。
5.2 动图演示
5.3 算法分析
和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间，其空间复杂度为O(n) 。
5.4 代码实现
1、Python语言实现
def mergeSort(arr):
import math
if(len(arr)<2):
return arr
middle = math.floor(len(arr)/2)
left, right = arr[0:middle], arr[middle:]
return merge(mergeSort(left), mergeSort(right))
def merge(left,right):
result = []
while left and right:
if left[0] <= right[0]:
result.append(left.pop(0));
else:
result.append(right.pop(0));
while left:
result.append(left.pop(0));
while right:
result.append(right.pop(0));
return result2、C++语言实现
// 归并排序
void MergeSort(int arr[], int start, int end, int * temp) // start和end分别是左边界和右边界
{
if (start >= end)
return;
int mid = (start + end) / 2;
MergeSort(arr, start, mid, temp);
MergeSort(arr, mid + 1, end, temp);
// 合并两个有序序列
int length = 0; // 表示辅助空间有多少个元素
int i_start = start;
int i_end = mid;
int j_start = mid + 1;
int j_end = end;
while (i_start <= i_end && j_start <= j_end)
{
if (arr[i_start] < arr[j_start])
{
temp[length] = arr[i_start];
length++;
i_start++;
}
else
{
temp[length] = arr[j_start];
length++;
j_start++;
}
}
while (i_start <= i_end) // 把剩下数的合并
{
temp[length] = arr[i_start];
i_start++;
length++;
}
while (j_start <= j_end)
{
temp[length] = arr[j_start];
length++;
j_start++;
}
// 把辅助空间的数据放到原空间
for (int i = 0; i < length; i++)
{
arr[start + i] = temp[i];
}
}
3、Java语言实现
public class MergeSort {
// 归并排序
public static int[] mergeSort(int[] arr, int left, int right) {
// 如果 left == right，表示数组只有一个元素，则不用递归排序
if (left < right) {
// 把大的数组分隔成两个数组
int mid = (left + right) / 2;
// 对左半部分进行排序
arr = mergeSort(arr, left, mid);
// 对右半部分进行排序
arr = mergeSort(arr, mid + 1, right);
//进行合并
merge(arr, left, mid, right);
}
return arr;
}
// 合并函数，把两个有序的数组合并起来
// arr[left..mif]表示一个数组，arr[mid+1 .. right]表示一个数组
private static void merge(int[] arr, int left, int mid, int right) {
//先用一个临时数组把他们合并汇总起来
int[] a = new int[right - left + 1];
int i = left;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= right) {
if (arr[i] < arr[j]) {
a[k++] = arr[i++];
} else {
a[k++] = arr[j++];
}
}
while(i <= mid) a[k++] = arr[i++];
while(j <= right) a[k++] = arr[j++];
// 把临时数组复制到原数组
for (i = 0; i < k; i++) {
arr[left++] = a[i];
}
}
}6 快速排序
快速排序（Quick Sort）是由东尼·霍尔所发展的一种排序算法。快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。
6.1 算法描述
① 从数列中挑出一个元素，称为 “基准”（pivot）;
② 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
③ 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
6.2 动图演示
6.3 算法分析
在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。
6.4 代码实现
1、Python语言实现
def quickSort(arr, left=None, right=None):
left = 0 if not isinstance(left,(int, float)) else left
right = len(arr)-1 if not isinstance(right,(int, float)) else right
if left < right:
partitionIndex = partition(arr, left, right)
quickSort(arr, left, partitionIndex-1)
quickSort(arr, partitionIndex+1, right)
return arr
def partition(arr, left, right):
pivot = left
index = pivot+1
i = index
while i <= right:
if arr[i] < arr[pivot]:
swap(arr, i, index)
index+=1
i+=1
swap(arr,pivot,index-1)
return index-1
def swap(arr, i, j):
arr[i], arr[j] = arr[j], arr[i]2、C++语言实现
// 快速排序
void QuickSort(int arr[], int start, int end)
{
if (start >= end)
return;
int i = start;
int j = end;
// 基准数
int baseval = arr[start];
while (i < j)
{
// 从右向左找比基准数小的数
while (i < j && arr[j] >= baseval)
{
j--;
}
if (i < j)
{
arr[i] = arr[j];
i++;
}
// 从左向右找比基准数大的数
while (i < j && arr[i] < baseval)
{
i++;
}
if (i < j)
{
arr[j] = arr[i];
j--;
}
}
// 把基准数放到i的位置
arr[i] = baseval;
// 递归
QuickSort(arr, start, i - 1);
QuickSort(arr, i + 1, end);
}3、Java语言实现
public class QuickSort {
public static int[] quickSort(int[] arr, int left, int right) {
if (left < right) {
//获取中轴元素所处的位置
int mid = partition(arr, left, right);
//进行分割
arr = quickSort(arr, left, mid - 1);
arr = quickSort(arr, mid + 1, right);
}
return arr;
}
private static int partition(int[] arr, int left, int right) {
//选取中轴元素
int pivot = arr[left];
int i = left + 1;
int j = right;
while (true) {
// 向右找到第一个小于等于 pivot 的元素位置
while (i <= j && arr[i] <= pivot) i++;
// 向左找到第一个大于等于 pivot 的元素位置
while(i <= j && arr[j] >= pivot ) j--;
if(i >= j)
break;
//交换两个元素的位置，使得左边的元素不大于pivot,右边的不小于pivot
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
arr[left] = arr[j];
// 使中轴元素处于有序的位置
arr[j] = pivot;
return j;
}
}7 堆排序
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：
大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
7.1 算法描述
① 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
② 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
③ 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
7.2 动图演示
7.3 算法分析
理想和非理想情况下，该排序算法的时间复杂度都是O(n2）。
7.4 代码实现
1、Python语言实现
def buildMaxHeap(arr):
import math
for i in range(math.floor(len(arr)/2),-1,-1):
heapify(arr,i)
def heapify(arr, i):
left = 2*i+1
right = 2*i+2
largest = i
if left < arrLen and arr[left] > arr[largest]:
largest = left
if right < arrLen and arr[right] > arr[largest]:
largest = right
if largest != i:
swap(arr, i, largest)
heapify(arr, largest)
def swap(arr, i, j):
arr[i], arr[j] = arr[j], arr[i]
def heapSort(arr):
global arrLen
arrLen = len(arr)
buildMaxHeap(arr)
for i in range(len(arr)-1,0,-1):
swap(arr,0,i)
arrLen -=1
heapify(arr, 0)
return arr2、C++语言实现
#include <stdio.h>
#include <stdlib.h>
void swap(int *a, int *b) {
int temp = *b;
*b = *a;
*a = temp;
}
void max_heapify(int arr[], int start, int end) {
// 建立父节点指标和子节点指标
int dad = start;
int son = dad * 2 + 1;
while (son <= end) { // 若子节点指标在范围內才做比较
if (son + 1 <= end && arr[son] < arr[son + 1]) // 先比较两个子节点大小，选择最大的
son++;
if (arr[dad] > arr[son]) //如果父节点大于子节点代表调整完毕，直接跳出函数
return;
else { // 否则交换父子內容再继续子节点和父节点比较
swap(&arr[dad], &arr[son]);
dad = son;
son = dad * 2 + 1;
}
}
}
void heap_sort(int arr[], int len) {
int i;
// 初始化，i从最后一个父节点开始调整
for (i = len / 2 - 1; i >= 0; i--)
max_heapify(arr, i, len - 1);
// 先将第一个元素和已排好元素前一位做交换，再重新调整，直到排序完毕
for (i = len - 1; i > 0; i--) {
swap(&arr[0], &arr[i]);
max_heapify(arr, 0, i - 1);
}
}
int main() {
int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
int len = (int) sizeof(arr) / sizeof(*arr);
heap_sort(arr, len);
int i;
for (i = 0; i < len; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
3、Java语言实现
public class Head {
// 堆排序
public static int[] headSort(int[] arr) {
int n = arr.length;
//构建大顶堆
for (int i = (n - 2) / 2; i >= 0; i--) {
downAdjust(arr, i, n - 1);
}
//进行堆排序
for (int i = n - 1; i >= 1; i--) {
// 把堆顶元素与最后一个元素交换
int temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
// 把打乱的堆进行调整，恢复堆的特性
downAdjust(arr, 0, i - 1);
}
return arr;
}
//下沉操作
public static void downAdjust(int[] arr, int parent, int n) {
//临时保存要下沉的元素
int temp = arr[parent];
//定位左孩子节点的位置
int child = 2 * parent + 1;
//开始下沉
while (child <= n) {
// 如果右孩子节点比左孩子大，则定位到右孩子
if(child + 1 <= n && arr[child] < arr[child + 1])
child++;
// 如果孩子节点小于或等于父节点，则下沉结束
if (arr[child] <= temp ) break;
// 父节点进行下沉
arr[parent] = arr[child];
parent = child;
child = 2 * parent + 1;
}
arr[parent] = temp;
}
}8 计数排序
计数排序（Counting Sort）不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
8.1 算法描述
① 找出待排序的数组中最大和最小的元素；
② 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
③ 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
④ 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
8.2 动图演示
8.3 算法分析
计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。
8.4 代码实现
1、Python语言实现
def countingSort(arr, maxValue):
bucketLen = maxValue+1
bucket = [0]*bucketLen
sortedIndex =0
arrLen = len(arr)
for i in range(arrLen):
if not bucket[arr[i]]:
bucket[arr[i]]=0
bucket[arr[i]]+=1
for j in range(bucketLen):
while bucket[j]>0:
arr[sortedIndex] = j
sortedIndex+=1
bucket[j]-=1
return arr2、C++语言实现
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void print_arr(int *arr, int n) {
int i;
printf("%d", arr[0]);
for (i = 1; i < n; i++)
printf(" %d", arr[i]);
printf("\n");
}
void counting_sort(int *ini_arr, int *sorted_arr, int n) {
int *count_arr = (int *) malloc(sizeof(int) * 100);
int i, j, k;
for (k = 0; k < 100; k++)
count_arr[k] = 0;
for (i = 0; i < n; i++)
count_arr[ini_arr[i]]++;
for (k = 1; k < 100; k++)
count_arr[k] += count_arr[k - 1];
for (j = n; j > 0; j--)
sorted_arr[--count_arr[ini_arr[j - 1]]] = ini_arr[j - 1];
free(count_arr);
}
int main(int argc, char **argv) {
int n = 10;
int i;
int *arr = (int *) malloc(sizeof(int) * n);
int *sorted_arr = (int *) malloc(sizeof(int) * n);
srand(time(0));
for (i = 0; i < n; i++)
arr[i] = rand() % 100;
printf("ini_array: ");
print_arr(arr, n);
counting_sort(arr, sorted_arr, n);
printf("sorted_array: ");
print_arr(sorted_arr, n);
free(arr);
free(sorted_arr);
return 0;
}
3、Java语言实现
public class Counting {
public static int[] countSort(int[] arr) {
if(arr == null || arr.length < 2) return arr;
int n = arr.length;
int max = arr[0];
// 寻找数组的最大值
for (int i = 1; i < n; i++) {
if(max < arr[i])
max = arr[i];
}
//创建大小为max的临时数组
int[] temp = new int[max + 1];
//统计元素i出现的次数
for (int i = 0; i < n; i++) {
temp[arr[i]]++;
}
int k = 0;
//把临时数组统计好的数据汇总到原数组
for (int i = 0; i <= max; i++) {
for (int j = temp[i]; j > 0; j--) {
arr[k++] = i;
}
}
return arr;
}
}9 桶排序
桶排序（Bucket Sort）是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。
为了使桶排序更加高效，我们需要做到这两点： 在额外空间充足的情况下，尽量增大桶的数量；使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中。同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。
9.1 算法描述
① 设置一个定量的数组当作空桶；
② 遍历输入数据，并且把数据一个一个放到对应的桶里去；
③ 对每个不是空的桶进行排序；
④ 从不是空的桶里把排好序的数据拼接起来。
9.2 动图演示
9.3 算法分析
桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。
什么时候最快？
当输入的数据可以均匀的分配到每一个桶中，时间复杂度O(n+k)。
什么时候最慢？
当输入的数据被分配到了同一个桶中，时间复杂度O(n2)。
9.4 代码实现
1、Python语言实现
def bucket_sort(array):
min_num, max_num = min(array), max(array)
bucket_num = (max_num-min_num)//3 + 1
buckets = [[] for _ in range(int(bucket_num))]
for num in array:
buckets[int((num-min_num)//3)].append(num)
new_array = list()
for i in buckets:
for j in sorted(i):
new_array.append(j)
return new_array2、C++语言实现
#include <bits/stdc++.h>
using namespace std;
// 打印数组
void print_array(int *arr, int n) {
if(n==0){
printf("ERROR: Array length is ZERO\n");
return;
}
printf("%d", arr[0]);
for (int i=1; i<n; i++)
printf(" %d", arr[i]);
printf("\n");
}
int* sort_array(int *arr, int n) {
int i;
int maxValue = arr[0];
for (i = 1; i < n; i++)
if (arr[i] > maxValue) // 输入数据的最大值
maxValue = arr[i];
// 设置10个桶，依次0，1，，，9
const int bucketCnt = 10;
vector<int> buckets[bucketCnt];
// 桶的大小bucketSize根据数组最大值确定：比如最大值99， 桶大小10
// 最大值999，桶大小100
// 根据最高位数字映射到相应的桶，映射函数为 arr[i]/bucketSize
int bucketSize = 1;
while (maxValue) { //求最大尺寸
maxValue /= 10;
bucketSize *= 10;
}
bucketSize /= 10; //桶的个数
// 入桶
for (int i=0; i<n; i++) {
int idx = arr[i]/bucketSize; //放入对应的桶
buckets[idx].push_back(arr[i]);
// 对该桶使用插入排序(因为数据过少，插入排序即可)，维持该桶的有序性
for (int j=int(buckets[idx].size())-1; j>0; j--) {
if (buckets[idx][j]<buckets[idx][j-1]) {
swap(buckets[idx][j], buckets[idx][j-1]);
}
}
}
// 顺序访问桶，得到有序数组
for (int i=0, k=0; i<bucketCnt; i++) {
for (int j=0; j<int(buckets[i].size()); j++) {
arr[k++] = buckets[i][j];
}
}
return arr;
}
int main() {
int n;
scanf("%d", &n);
int *arr;
arr = (int*)malloc(sizeof(int)*n);
for (int i=0; i<n; i++) scanf("%d", &arr[i]);
arr = sort_array(arr, n);
print_array(arr, n);
system("pause");
return 0;
}3、Java语言实现
public class BucketSort {
public static int[] BucketSort(int[] arr) {
if(arr == null || arr.length < 2) return arr;
int n = arr.length;
int max = arr[0];
int min = arr[0];
// 寻找数组的最大值与最小值
for (int i = 1; i < n; i++) {
if(min > arr[i])
min = arr[i];
if(max < arr[i])
max = arr[i];
}
//和优化版本的计数排序一样，弄一个大小为 min 的偏移值
int d = max - min;
//创建 d / 5 + 1 个桶，第 i 桶存放 5*i ~ 5*i+5-1范围的数
int bucketNum = d / 5 + 1;
ArrayList<LinkedList<Integer>> bucketList = new ArrayList<>(bucketNum);
//初始化桶
for (int i = 0; i < bucketNum; i++) {
bucketList.add(new LinkedList<Integer>());
}
//遍历原数组，将每个元素放入桶中
for (int i = 0; i < n; i++) {
bucketList.get((arr[i]-min)/d).add(arr[i] - min);
}
//对桶内的元素进行排序，我这里采用系统自带的排序工具
for (int i = 0; i < bucketNum; i++) {
Collections.sort(bucketList.get(i));
}
//把每个桶排序好的数据进行合并汇总放回原数组
int k = 0;
for (int i = 0; i < bucketNum; i++) {
for (Integer t : bucketList.get(i)) {
arr[k++] = t + min;
}
}
return arr;
}
}10 基数排序
基数排序（Radix Sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
10.1 算法描述
① 取得数组中的最大数，并取得位数；
② arr为原始数组，从最低位开始取每个位组成radix数组；
③ 对radix进行计数排序（利用计数排序适用于小范围数的特点）；
10.2 动图演示
10.3 算法分析
理想和非理想情况下，该排序算法的时间复杂度都是时间复杂度：O(kn)。
基数排序基于分别排序，分别收集，所以是稳定的。但基数排序的性能比桶排序要略差，每一次关键字的桶分配都需要O(n)的时间复杂度，而且分配之后得到新的关键字序列又需要O(n)的时间复杂度。假如待排数据可以分为d个关键字，则基数排序的时间复杂度将是O(d*2n) ，当然d要远远小于n，因此基本上还是线性级别的。
基数排序的空间复杂度为O(n+k)，其中k为桶的数量。一般来说n>>k，因此额外空间需要大概n个左右。
10.4 代码实现
1、Python语言实现
def radix_sort(array):
max_num = max(array)
place = 1
while max_num >= 10**place:
place += 1
for i in range(place):
buckets = [[] for _ in range(10)]
for num in array:
radix = int(num/(10**i) % 10)
buckets[radix].append(num)
j = 0
for k in range(10):
for num in buckets[k]:
array[j] = num
j += 1
return array2、C++语言实现
#include<bits/stdc++.h>
using namespace std;
// Function that performs Radix Sort
void radix_sort(int arr[], int n){
// Step 1: Find the maxumum element
int maximum = arr[0];
for(int i=1;i<n;i++){
maximum = max(maximum, arr[i]);
}
// Step 2: Count the number of digits of the maximum number
int digits = 0;
while(maximum > 0){
digits++;
maximum /= 10;
}
// Step 3, 4, 5: Arrange the numbers on the basis of digits
for(int i=0;i<digits;i++){
// Units/Tens/Hundreds - used to determine which digit
int power = pow(10, i);
// Holds the updated array
int new_array[n];
// Counting Sort Array - required for arranging digits [0-9]
int count[10];
// Initializing Count Array
memset(count, 0, sizeof(count));
// Calculating frequency of digits
for(int j=0;j<n;j++){
// The digit under consideration in this iteration
int num = (arr[j]/power) % 10;
count[num]++;
}
// Cumulative frequency of count array
for(int j=1;j<10;j++){
count[j] += count[j-1];
}
// Designating new positions in the updated array
for(int j=n-1;j>=0;j--){
// The digit under consideration in this iteration
int num = (arr[j]/power) % 10;
new_array[count[num]-1] = arr[j];
count[num]--;
}
// Updating the original array using New Array
for(int j=0;j<n;j++)
arr[j] = new_array[j];
}
// Printing the sorted array
for(int j=0;j<n;j++)
cout<<arr[j]<<" ";
cout<<endl;
}
// The main function
int main(){
// The array containing values to be sorted
int arr[] = {15, 120, 53, 36, 167, 81, 75, 32, 9, 60};
// Size of the array
int n = sizeof(arr)/sizeof(n);
// Function call for the Radix Sort Algorithm
radix_sort(arr, n);
return 1;
}3、Java语言实现
public class RadixSort {
public static int[] radioSort(int[] arr) {
if(arr == null || arr.length < 2) return arr;
int n = arr.length;
int max = arr[0];
// 找出最大值
for (int i = 1; i < n; i++) {
if(max < arr[i]) max = arr[i];
}
// 计算最大值是几位数
int num = 1;
while (max / 10 > 0) {
num++;
max = max / 10;
}
// 创建10个桶
ArrayList<LinkedList<Integer>> bucketList = new ArrayList<>(10);
//初始化桶
for (int i = 0; i < 10; i++) {
bucketList.add(new LinkedList<Integer>());
}
// 进行每一趟的排序，从个位数开始排
for (int i = 1; i <= num; i++) {
for (int j = 0; j < n; j++) {
// 获取每个数最后第 i 位是数组
int radio = (arr[j] / (int)Math.pow(10,i-1)) % 10;
//放进对应的桶里
bucketList.get(radio).add(arr[j]);
}
//合并放回原数组
int k = 0;
for (int j = 0; j < 10; j++) {
for (Integer t : bucketList.get(j)) {
arr[k++] = t;
}
//取出来合并了之后把桶清光数据
bucketList.get(j).clear();
}
}
return arr;
}
}