排序算法

本篇博客仅给出 $6$ 种基础排序算法的原理、时间复杂度分析和代码实现（$C$++，$Python$ 和 $Java$），其他更高级的排序算法一般都要依托一些高级一点的数据结构，这里就不再细说了。
1. 冒泡排序
 1.1 冒泡排序-算法原理
 1.2 冒泡排序-时间复杂度分析
 1.3 冒泡排序-代码实现
2. 选择排序
 2.1 选择排序-算法原理
 2.2 选择排序-时间复杂度分析
 2.3 选择排序-代码实现
3. 插入排序
 3.1 插入排序-算法原理
 3.2 插入排序-时间复杂度分析
 3.3 插入排序-代码实现
4. 快速排序
 4.1 快速排序-算法原理
 4.2 快速排序-时间复杂度分析
 4.3 快速排序-代码实现
5. 归并排序
 5.1 归并排序-算法原理
 5.2 归并排序-时间复杂度分析
 5.3 归并排序-代码实现
6. 希尔排序
 6.1 希尔排序-算法原理
 6.2 希尔排序-时间复杂度分析
 6.3 希尔排序-代码实现

1. 冒泡排序

算法原理

冒泡排序在所有排序算法中，属于比较基础的一种。它的原理就是通过遍历待排序元素列，依次比较相邻元素，按照一定的规则调整它们的顺序（如何复合规则，则继续遍历），直至排序完毕。
一般来说，这个算法都是用来针对数组排序，而且往往最终结果都是非降序排列的，因此狭义地来说，冒泡排序可以归纳为：
a. 比较相邻元素，若前者大于后者，则进行交换；
b. 对每一组相邻元素重复操作a，从第 $1$ 对到第 $n-1$ 对，此时，数组中最大的元素已经沉到数组最底部了；
c. 此时可以将最后一个元素抛开，针对前 $n-1$ 个元素组成的数组继续执行操作a和b；
d. 持续上述操作，满足达到遍历轮数。

这里我们结合一个具体的例子来理解一下冒泡排序：有数组 A = { 5 , 4 , 3 , 2 , 1 } A={5,4,3,2,1} A={5,4,3,2,1}，利用冒泡排序将其调整为非降序排列。

初始状态	{ 5 , 4 , 3 , 2 , 1 } {5,4,3,2,1} {5,4,3,2,1}
第一轮排序	5 > 4 → { 4 , 5 , 3 , 2 , 1 } 5 > 3 → { 4 , 3 , 5 , 2 , 1 } 5 > 2 → { 4 , 3 , 2 , 5 , 1 } 5 > 1 → { 4 , 3 , 2 , 1 , 5 } 5>4rightarrow{4,5,3,2,1}\\5>3rightarrow{4,3,5,2,1}\\5>2rightarrow{4,3,2,5,1}\\5>1rightarrow{4,3,2,1,5} 5>4→{4,5,3,2,1}5>3→{4,3,5,2,1}5>2→{4,3,2,5,1}5>1→{4,3,2,1,5}

第一轮排序结束之后，数组的最大元素一定沉到了数组的末尾，那么，接下来的第二轮排序只需要针对 { 4 , 3 , 2 , 1 } {4,3,2,1} {4,3,2,1} 进行即可，以此类推，第四轮排序结束之后，数组已是非降序。下面来看算法：
—————————-——$bubble\_sort$——————————————

• 输入：待排序元素列 $A[1\dots n]$ 和数组长度
• 输出：非降序排列元素列（实际上这里的规则可以自定义，在对应的代码部分做好修改即可，但一般都是非降序数组）
• $bubble\_sort(A[1\dots n],n)$
• 过程：
• 1.   f o r    i ← 1    t o    n − 1    { hspace{1cm}1.space forspacespace ileftarrow1spacespace tospacespace n-1spacespace{ 1. for  i←1  to  n−1  {表示遍历的轮数，即一共遍历 $n-1$ 轮$\}$
• 2.   f o r    j ← 1    t o    n − i − 1    { hspace{1cm}2.spacehspace{1cm}forspacespace jleftarrow1spacespace tospacespace n-i-1spacespace{ 2. for  j←1  to  n−i−1  {最大的元素渐渐沉到末尾，小的元素向上浮$\}$
• $3.ifA[j]>A[j+1]then$
• $4.tmp\leftarrow A[j]$
• $5.A[j]\leftarrow A[j+1]$
• $6.A[j+1]\leftarrow tmp$
• $7.endif$
• $8.endfor$
• $9.endfor$

————————————————————————————————

复杂度分析

最好情况：数组一开始就是非降序排列的，那么一趟扫描就可以完成排序，元素比较次数为 $C=C_{min}=n-1$，记录移动次数 $M=M_{min}=0$，因此，最好情况下的时间复杂度为 $O(n)$。
最坏情况：例如上述例子，数组一开始是非升序排列的，那么需要进行 $n-1$ 轮遍历，每轮遍历需要执行 $n-i(1⩽i⩽n-1)$ 次元素比较，有 $C=C_{max}=\frac{n(n-1)}{2}=O(n^2)$；另外每次比较都伴随着记录的三次移动，又有 $M=M_{max}=\frac{3n(n-1)}{2}=O(n^2)$，因此，最坏情况下的时间复杂度为 $O(n^2)$。
综上，我们可以认为冒泡排序的平均时间复杂度为 $O(n^2)$。

实现

$C$++

void bubble_sort(int A[], int n){
	for(int i=0; i<n-1; i++){
		for(int j=0; j<n-i-1; j++){
			if(A[j] > A[j+1]){
				int tmp = A[j];
				A[j] = A[j+1];
				A[j+1] = tmp;
			}
		}
	}
}

$Python$

def bubble_sort(A, n):
	for i in range(0, n-1):
		for j in range(0, n-i-1):
			if A[j] > A[j+1]:
				tmp = A[j]
				A[j] = A[j+1]
				A[j+1] = tmp
	return A

$Java$

public static void bubbleSort(int[] A, int n){
	for(int i=0; i<n-1; i++){
		for(int j=0; j<n-i-1; j++){
			if(A[j] > A[j+1]){
				int tmp = A[j];
				A[j] = A[j+1];
				A[j+1] = tmp;
			}
		}
	}
}

表格分割线

2. 选择排序

算法原理

选择排序的基本思路比较直观（这里只了解基本排序排序，实际上可以借助树等数据结构进行改写），现在假设 $A[1\dots n]$ 为一个有 $n$ 个元素的数组，需要对其按非降序规则进行排序，那么我们可以先遍历数组，找到其中最小的元素，然后将其与 $A[1]$ 进行交换；然后遍历剩下的 $n-1$ 个元素 $(A[2\dots n])$ 中最小的元素，将其与 $A[2]$ 进行交换；重复操作直至完成 $A[n-1]$ 的交换，此时 $A[n]$ 中已经存储数组 $A[1\dots n]$ 中最大的元素，即数组排序完毕。直接看算法：
—————————-——$selection\_sort$——————————————

• 输入：待排序数组 $A[1\dots n]$ 和数组长度
• 输出：非降序排列数组 $A[1\dots n]$
• $selection\_sort(A[1\dots n],n)$
• 过程：
• 1.   f o r    i ← 1    t o    n − 1    { hspace{1cm}1.space forspacespace ileftarrow1spacespace tospacespace n-1spacespace{ 1. for  i←1  to  n−1  {依次找到前 $n-1$ 小的数组元素$\}$
• $2.k\leftarrow i$
• 3. f o r    j ← i + 1    t o    n    { hspace{1cm}3.hspace{1cm}forspacespace jleftarrow i+1spacespace tospacespace nspacespace{ 3.for  j←i+1  to  n  {查找第 $i$ 小的元素$\}$
• $4.ifA[j]<A[k]thenk\leftarrow j$
• $5.endfor$
• $6.ifk\ne ithen$
• $7.tmp=A[i]$
• $8.A[i]=A[k]$
• $9.A[k]=tmp$
• $10.endif$
• $11.endfor$

————————————————————————————————

复杂度分析

这里我们将最好情况和最坏情况放在一起看，易知该算法执行的元素比较次数为
${\sum }_{i=1}^{n-1}(n-i)=(n-1)+(n-2)+\cdots +1={\sum }_{i=1}^{n-1}i=\frac{n(n-1)}{2}$
也可以看出元素交换的次数介于 $0\sim n-1$ 之间，由于每次交换都伴随着记录的三次移动，因此可知记录移动次数介于 $0\sim 3(n-1)$ 之间。
综上，基本选择排序算法的时间复杂度为 $O(n^2)$。

实现

$C$++

void selection_sort(int A[], int n){
	for(int i=0; i<n-1; i++){
		int k = i;
		for(int j=i+1; j<n; j++){
			if(A[j] < A[k]) k = j;
		}
		if(k != i){
			int tmp = A[i];
			A[i] = A[k];
			A[k] = tmp;
		}
	}
}

$Python$

def selection_sort(A, n):
	for i in range(0, n-1):
		k = i
		for j in range(i+1, n):
			if A[j] < A[k]:
				k = j
		if k != i:
			tmp = A[i]
			A[i] = A[k]
			A[k] = tmp
	return A

$Java$

public static void selectionSort(int[] A, int n){
	for(int i=0; i<n-1; i++){
		int k = i;
		for(int j=i+1; j<n; j++){
			if(A[j] < A[k]) k = j;
		}
		if(k != i){
			int tmp = A[i];
			A[i] = A[k];
			A[k] = tmp;
		}
	}
}

表格分割线

3. 插入排序

算法原理

插入排序依赖于已经有序的元素序列，它的核心要义就是——在已经排序完毕的元素序列中插入指定元素，并且插入元素之后不破坏原有的排列规则。这里是直接插入排序的算法思路：
从大小为 $1$ 的子数组 $A[1]$ 开始，显然该数组已经排序完毕；
接下来需要插入 $A[2]$：比较 $A[1]$ 和 $A[2]$ 的大小，根据排序规则选择将 $A[2]$ 插入到 $A[1]$ 的前面或者后面；
重复插入操作，那么在第 $i$ 次操作中，我们需要将 $A[i]$ 插入到已经排序完毕的子数组 $A[1\dots i-1]$ 中的合适位置：遍历第 $i-1\sim 1$ 号元素，每次都将 $A[i]$ 同当前位置的元素进行比较。遍历的每一步，元素都会被移动到序号更高的位置上，这样重复比较操作和移位操作直至找到一个小于 $A[i]$ 的元素，或者已经排序完毕的数组被全部遍历完，此时，$A[i]$ 就已经被插入到合适的位置上了。下面我们根据一个例子来简单理解一下该算法执行的过程：

初始值排序	{ 12 } 15 , 9 , 20 , 6 , 31 , 24 {12}hspace{1cm}15,9,20,6,31,24 {12}15,9,20,6,31,24
第一次插入排序	{ 12 , 15 } 9 , 20 , 6 , 31 , 24 {12,15}hspace{1cm}9,20,6,31,24 {12,15}9,20,6,31,24
第二次插入排序	{ 9 , 12 , 15 } 20 , 6 , 31 , 24 {9,12,15}hspace{1cm}20,6,31,24 {9,12,15}20,6,31,24
第三次插入排序	{ 9 , 12 , 15 , 20 } 6 , 31 , 24 {9,12,15,20}hspace{1cm}6,31,24 {9,12,15,20}6,31,24
第四次插入排序	{ 6 , 9 , 12 , 15 , 20 } 31 , 24 {6,9,12,15,20}hspace{1cm}31,24 {6,9,12,15,20}31,24
第五次插入排序	{ 6 , 9 , 12 , 15 , 20 , 31 } 24 {6,9,12,15,20,31}hspace{1cm}24 {6,9,12,15,20,31}24
第六次插入排序	{ 6 , 9 , 12 , 15 , 20 , 24 , 31 } {6,9,12,15,20,24,31} {6,9,12,15,20,24,31}

算法具体步骤：
—————————-——$insertion\_sort$——————————————

• 输入：待排序数组 $A[1\dots n]$ 和数组长度
• 输出：非降序排列数组 $A[1\dots n]$
• $insertion\_sort(A[1\dots n],n)$
• 过程：
• $1.fori\leftarrow 2ton$
• $2.x\leftarrow A[i]$
• $3.j\leftarrow i-1$
• 4. w h i l e    ( j > 0 )    a n d    ( A [ j ] > x )    { hspace{1cm}4.hspace{1cm}whilespacespace(j>0)spacespace andspacespace (A[j]>x)spacespace{ 4.while  (j>0)  and  (A[j]>x)  {查找第 $i$ 个元素的插入位置$\}$
• $5.A[j+1]\leftarrow A[j]$
• $6.j\leftarrow j-1$
• $7.endwhile$
• $8.A[j+1]\leftarrow x$
• $9.endfor$

————————————————————————————————

复杂度分析

易知，元素比较的次数取决于输入元素的顺序。因此，
在最好情况下，数组已按非降序排列，元素的比较次数最少，为 $n-1$ 次；
在最坏情况下，数组按降序排列，并且所有元素各不相同，元素的比较次数最大，为${\sum }_{i=2}^n(i-1)={\sum }_{i=1}^{n-1}i=\frac{n(n-1)}{2}$
综上，直接插入排序算法的平均时间复杂度为 $O(n^2)$。

实现

$C$++

void insertion_sort(int A[], int n){
	for(int i=1; i<n; i++){
		int x = A[i], j = i-1;
		while(j>=0 && A[j]>x){
			A[j+1] = A[j];
			j--;
		}
		A[j+1] = x;
	}
}

$Python$

def insertion_sort(A, n):
	for i in range(1, n):
		x = A[i]
		j = i-1
		while (j>=0) and (A[j]>x):
			A[j+1] = A[j]
			j -= 1
		A[j+1] = x
	return A

$Java$

public static void insertionSort(int[] A, int n){
	for(int i=1; i<n; i++){
		int x = A[i], j = i-1;
		while(j>=0 && A[j]>x){
			A[j+1] = A[j];
			j--;
		}
		A[j+1] = x;
	}
}

表格分割线

4. 快速排序

算法原理

快速排序算法，实际上就是对冒泡排序的改进，它的核心思路就是先通过一次排序（遍历）将待排序元素序列 $A$ 分割成两个独立的子元素序列 $A_1,A_2$，其中 $A_1$ 中所有元素针对 $A_2$ 中所有元素都符合给定排序规则，然后对 $A_1,A_2$ 重复上述操作，易知整个排序过程都可以递归进行，根据上述原理我们可以得到如下排序流程：

• $(1)$ 设置分割点，用来分割待排序元素序列
• $(2)$ 结合分割点和排序规则将待排序元素序列分割为两个子序列
• $(3)$ 针对两个子序列分别执行操作：设置分割点，结合分割点和排序规则将子序列继续分割
• $(4)$ 重复上述操作，通过递归先将左侧部分排好序，再将右侧部分排好序，最终得到排序完毕的元素序列

可见快速排序算法主要借助的就是“分治”的思想。那么，如何“分”，就是该算法的重要前提：
划分算法：设 $A[1\dots n]$ 是一个实数数组，要求将其整理为非降序排列。
我们先来设置分割点 $ref$，一般来说都会默认为数组的第一个元素，即 $ref=A[1]$。下面就需要调整数组顺序，使得小于或等于 $ref$ 的元素都排在它前面，所有大于 $ref$ 的元素都排在它的后面。
例如有 e x = { 5 , 3 , 9 , 2 , 7 , 1 , 8 } ex={5,3,9,2,7,1,8} ex={5,3,9,2,7,1,8}，再执行完划分算法后就要得到 e x = { 1 , 3 , 2 , 5 , 7 , 9 , 8 } ex={1,3,2,5,7,9,8} ex={1,3,2,5,7,9,8}。但是，这又是如何得到的呢？实际上有很多策略都可以实现划分，但是上述的例子中，采取的是如下算法：

• 输入：数组 $A[low,high]$
• 输出：新数组 $A$ 和 $ref=A[low]$ 的在新数组中的位置
• $1.i\leftarrow low$
• $2.ref\leftarrow A[low]$
• $3.forj\leftarrow low+1tohigh$
• $4.ifA[j]⩽refthen$
• $5.i\leftarrow i+1$
• $6.ifi\ne jthenswap(A[i],A[j])$
• $7.endif$
• $8.endfor$
• $9.swap(A[low],A[i])$
• $10.w\leftarrow i$
• $11.returnAandw$

上述算法在执行过程中主要利用 $i,j$ 指针，先将其设置为 $i=low,j=low+1$，然后借助 $for$ 循环遍历数组，$for$ 循环执行结束后得到：

1. $A[low]=ref$
2. $A[k]⩽ref,low⩽k⩽i$
3. $A[k]>ref,i<k⩽j$

最后再将 $A[i]$ 与 $ref$ 交换，这样就得到了我们期待的新数组。下面我们根据一个例子来具体看一下划分算法的执行步骤：

初始值情况	{ 5 , 7 , 1 , 6 , 4 , 8 , 3 , 2 } {5,7,1,6,4,8,3,2} {5,7,1,6,4,8,3,2} 此时有 $low=1,high=8,ref=5$
$(1)$	$i=low,A[i]=5;j=low+1,A[j]=7$
$(2)$	$j=3$ 时 A [ 3 ] = 1 ⩽ r e f = 5 ⇒ i = 2 ≠ j ⇒ { 5 , 1 , 7 , 6 , 4 , 8 , 3 , 2 } A[3]=1leqslant ref=5Rightarrow i=2neq jRightarrow{5,1,7,6,4,8,3,2} A[3]=1⩽ref=5⇒i=2​=j⇒{5,1,7,6,4,8,3,2}
$(3)$	$j=5$ 时 A [ 5 ] = 4 ⩽ r e f = 5 ⇒ i = 3 ≠ j ⇒ { 5 , 1 , 4 , 6 , 7 , 8 , 3 , 2 } A[5]=4leqslant ref=5Rightarrow i=3neq jRightarrow{5,1,4,6,7,8,3,2} A[5]=4⩽ref=5⇒i=3​=j⇒{5,1,4,6,7,8,3,2}
$(4)$	$j=7$ 时 A [ 7 ] = 3 ⩽ r e f = 5 ⇒ i = 4 ≠ j ⇒ { 5 , 1 , 4 , 3 , 7 , 8 , 6 , 2 } A[7]=3leqslant ref=5Rightarrow i=4neq jRightarrow{5,1,4,3,7,8,6,2} A[7]=3⩽ref=5⇒i=4​=j⇒{5,1,4,3,7,8,6,2}
$(5)$	$j=8$ 时 A [ 8 ] = 2 ⩽ r e f = 5 ⇒ i = 5 ≠ j ⇒ { 5 , 1 , 4 , 3 , 2 , 8 , 6 , 7 } A[8]=2leqslant ref=5Rightarrow i=5neq jRightarrow{5,1,4,3,2,8,6,7} A[8]=2⩽ref=5⇒i=5​=j⇒{5,1,4,3,2,8,6,7}
$(6)$	$j=8=high\Rightarrow$ $for$ 循环停止
$(7)$	s w a p ( A [ l o w ] , A [ i ] ) ⇒ { 2 , 1 , 4 , 3 , 5 , 8 , 6 , 7 } swap(A[low],A[i])Rightarrow{2,1,4,3,5,8,6,7} swap(A[low],A[i])⇒{2,1,4,3,5,8,6,7}
$(8)$	算法执行完毕

最后注意到上述算法仅仅用到一个额外变量来存储它的局部变量，因此该划分算法的空间复杂度为 $\Theta (1)$。下面，我们就可以结合划分算法，借助递归调用完成快速排序的算法设计：

—————————-——$quick\_sort$——————————————

• 输入：待排序数组 $A[1\dots n]$ 和数组起始下标索引
• 输出：非降序排列数组 $A[1\dots n]$
• $quick\_sort(A[1\dots n],1,n)$
• 过程：$quick\_sort(A,low,high)$
• $1.iflow<highthen$
• $2.i\leftarrow low$
• $3.ref\leftarrow A[low]$
• $4.forj\leftarrow low+1tohigh$
• $5.ifA[j]⩽refthen$
• $6.i\leftarrow i+1$
• $7.ifi\ne jthenswap(A[i],A[j])$
• $8.endif$
• $9.endfor$
• $10.swap(A[low],A[i])$
• $11.w\leftarrow i$
• $12.quick\_sort(A,low,w-1)$
• $13.quick\_sort(A,w+1,high)$
• $14.endif$

————————————————————————————————

复杂度分析

最坏情况

对于算法 $quick\_sort(A,low,high)$ 的每次调用，$ref=A[low]$ 都是数组中的最小值元素，那么仅仅存在一个有效的递归调用，而另一个调用就将作用在空数组上，即算法是由调用 $quick\_sort(A,1,n)$ 开始，下一步的两个递归调用分别是 $quick\_sort(A,1,0)$ 和 $quick\_sort(A,2,n)$，其中，第一个就是无效调用。
因此，若输入的待排序数组已经是非降序排列的，最坏情况就出现了。简单来说，下面对于 $quick\_sort(A,low,high)$ 过程的 $n$ 次调用将发生$quick\_sort(A,1,n),quick\_sort(A,2,n),\dots ,quick\_sort(A,n,n)$。
由于对于输入大小为 $j$ 的元素，划分算法执行的元素比较次数为 $j-1$，因此在最坏情况下，算法 $quick\_sort(A,low,high)$ 执行的元素总比较次数是
$(n-1)+(n-2)+\cdots +1+0=\frac{n(n-1)}{2}=\Theta (n^2)$
但是我们要注意一点，如果我们总是在线性时间内选择中项作为分割点 $ref$，最坏情况下的运行时间可以被改进为 $\Theta (n\log n)$，主要是因为这么划分元素是高度平衡的，而在这种情况下，两个递归调用具有几乎相同数目的元素，进而得到计算比较次数的递推式：
$C(n)=\{\begin{array}{l}0ifn=1\\ \\ 2C(\frac{n}{2})+\Theta (n)ifn>1\end{array}$
最终求得 $C(n)=\Theta (n\log n)$，但是找出中项的算法对时间复杂度的影响不可控，因而不值得与 $quick\_sort(A,low,high)$ 算法配合使用。

平均情况

我们必须承认最坏情况会在算法执行时发生，但是它同时也属于极端情况，即在实际情况下是很少发生的，因此用最坏情况下的算法运行时间来界定时间复杂度很不合理。下面来看看平均情况：
为了便于理解，我们假定输入数据是互不相同的（这是不失一般性的，因为算法的性能与输入数据值是无关的，有关系的是它们的相对次序），不如更进一步，我们直接假设进行排序的元素是前 $n$ 个正整数 $1,2,\dots ,n$。
在分析算法的平均性能的过程中，我们必须高度关注输入数据的概率分布，这里采用简化分析的方法，就假定元素的每个排列的出现是等可能的，即对于 $1,2,\dots ,n$ 的 $n!$ 种排列情况来说，每一个排列的出现是等可能的，这一点主要是为了确保数组中的每个数被选作 $ref$ 的可能性是一样的，即数组 $A$ 中任意元素被选为分割点的概率都是 $\frac{1}{n}$。设 $C(n)$ 为对于大小为 $n$ 的输入数据，$quick\_sort(A,low,high)$ 算法所执行的平均比较次数，结合上述假设和算法的具体设计，得到
$C(n)=(n-1)+\frac{1}{n}{\sum }_{w=1}^n(C(w-1)+C(n-w))$
$\because {\sum }_{w=1}^{n}C(n-w)=C(n-1)+C(n-2)+\cdots +C(0)={\sum }_{w=1}^{n}C(w-1)$
$\therefore C(n)=(n-1)+\frac{2}{n}{\sum }_{w=1}^{n}C(w-1)$
$\Rightarrow nC(n)=n(n-1)+2{\sum }_{w=1}^{n}C(w-1)$
$\Rightarrow (n-1)C(n-1)=(n-1)(n-2)+2{\sum }_{w=1}^{n-1}C(w-1)$
$\Rightarrow \frac{C(n)}{n+1}=\frac{C(n-1)}{n}+\frac{2(n-1)}{n(n+1)}=D(n)$
$\Rightarrow D(n)=D(n-1)+\frac{2(n-1)}{n(n+1)}andD(1)=0$
$\Rightarrow D(n)=2{\sum }_{j=1}^n\frac{j-1}{j(j+1)}$
$=2{\sum }_{j=1}^n\frac{2}{j+1}-2{\sum }_{j=1}^n\frac{1}{j}$
$=4{\sum }_{j=2}^{n+1}\frac{1}{j}-2{\sum }_{j=1}^n\frac{1}{j}$
$=2{\sum }_{j=1}^n\frac{1}{j}-\frac{4n}{n+1}$
$=2\ln n-\Theta (1)$
$=\frac{2}{\log e}\log n-\Theta (1)$
$\approx 1.44\log n$
$\Rightarrow C(n)=(n+1)D(n)\approx 1.44n\log n$

综上，我们可以得到 $quick\_sort$ 算法的时间复杂度为 $\Theta (n\log n)$。

实现

$C$++

void quick_sort(int A[], int low, int high){
	if(low < high){
		int i = low, ref = A[low];
		for(int j=low+1; j<=high; j++){
			if(A[j] <= ref){
				i++;
				if(i != j){
					int tmp_0 = A[i];
					A[i] = A[j];
					A[j] = tmp_0;
				}
			}
		}
		int tmp_1 = A[low];
		A[low] = A[i];
		A[i] = tmp_1;
		int w = i;
		quick_sort(A, low, w-1);
		quick_sort(A, w+1, high);
	}
}

$Python$

def quick_sort(A, low, high):
	if low < high:
		i, ref = low, A[low]
		for j in range(low+1, high+1):
			if A[j] <= ref:
				i += 1
				if i != j:
					tmp_0 = A[i]
					A[i] = A[j]
					A[j] = tmp_0

		tmp_1 = A[low]
		A[low] = A[i]
		A[i] = tmp_1
		w = i
		quick_sort(A, low, w-1)
		quick_sort(A, w+1, high)
		return A

$Java$

public static void quickSort(int[] A, int low, int high){
	if(low < high){
		int i = low, ref = A[low];
		for(int j=low+1; j<=high; j++){
			if(A[j] <= ref){
				i++;
				if(i != j){
					int tmp_0 = A[i];
					A[i] = A[j];
					A[j] = tmp_0;
				}
			}
		}
		int tmp_1 = A[low];
		A[low] = A[i];
		A[i] = tmp_1;
		int w = i;
		quickSort(A, low, w-1);
		quickSort(A, w+1, high);
	}
}

表格分割线

5. 归并排序

算法原理

归并排序算法是建立在归并操作上的一种有效的排序算法，该算法是分治思想设计算法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。在学习该算法之前，我们先来看一下何为归并操作：
现在假设有一个数组 $A[1\dots m],p,q,r$ 为其三个索引，并有 $1⩽p⩽q<r⩽m$，两个子数组 $A[p\dots q]$ 和 $A[q+1\dots r]$ 都按升序排列，合并这两个数组的过程，就是重新安排 $A$ 中元素的位置，使得子数组 $A[p\dots r]$ 也按升序排列。算法具体思路如下：
使用两个指针 $s,t$，在初始状态下，$s$ 指向 $A[p]$，$t$ 指向 $A[q+1]$，再利用一个空数组 $B[p\dots r]$ 作为暂存器。每一次比较元素 $A[s]$ 和 $A[t]$，将小的元素添加到暂存器中，若相同则添加 $A[s]$，然后再更新指针：若 $A[s]⩽A[t]$，则 $s$+=$1$，否则 $t$+=$1$。当条件 $s=q+1$ 或者 $t=r+1$ 满足时停止，若满足条件一，则把数组 $A[t\dots r]$ 中剩余的元素添加至 $B$ 中；若满足条件二，则把数组 $A[s\dots q]$ 中剩余的元素添加至 $B$ 中，最后再将暂存器数组 $B[p\dots r]$ 复制回 $A[p\dots r]$。实际上，该思路的核心就是同时遍历两个子数组，在比较之后将每个元素一一装到暂存器中，下面看伪代码：

• 输入：数组 $A[1\dots m]$ 和其三个索引 $p,q,r,1⩽p⩽q<r⩽m$，两个子数组 $A[p\dots q]$ 和 $A[q+1\dots r]$ 各自按升序排列。
• 输出：将子数组 $A[p\dots q]$ 和 $A[q+1\dots r]$ 合并为 $A[p\dots r]$
• $1.comment:B[p\dots r]$ 是一个辅助数组（暂存器）
• $2.s\leftarrow p;t\leftarrow q+1;k\leftarrow p$
• $3.whiles⩽qandt⩽r$
• $4.ifA[s]⩽A[t]then$
• $5.B[k]\leftarrow A[s]$
• $6.s\leftarrow s+1$
• $7.else$
• $8.B[k]\leftarrow A[t]$
• $9.t\leftarrow t+1$
• $10.endif$
• $11.k\leftarrow k+1$
• $12.endwhile$
• $13.ifs=q+1thenB[k\dots r]\leftarrow A[t\dots r]$
• $14.elseB[k\dots r]\leftarrow A[s\dots q]$
• $15.endif$
• $16.A[p\dots r]\leftarrow B[p\dots r]$

了解了归并操作，下面我们就可以来看一下归并排序算法的具体思路了。
假设有待排序数组 A [ 1 … 8 ] = { 9 , 4 , 5 , 2 , 1 , 7 , 4 , 6 } A[1dots8]={9,4,5,2,1,7,4,6} A[1…8]={9,4,5,2,1,7,4,6}，现在开始合并排序 $merge\_sort(A,1,8)$，调用该算法会引起一个隐含二叉树所表示的一系列递归调用，树的每个结点由上下两个数组组成，上面的数组是调用算法的输入，下面的数组则是调用算法的输出，换句话说，顶端数组是“分”后的待排序数组，底端数组是“治”后“再作组合”的数组。二叉树的每个边用表示控制流的两个相向的边取代，边上的标号指明这些递归调用发生的次序，显然，这个调用链顺序为：访问根、左子树和右子树，但是计算顺序略有不同：左子树、右子树、根。为了实现该算法，我们需要用一个栈来存储每次调用过程生成的局部数据。下面是图示：

现在，给出归并排序的伪代码：

—————————-——$merge\_sort$——————————————

• 输入：待排序数组 $A[1\dots n]$
• 输出：按非降序排列的数组 $A[1\dots n]$
• $1.merge\_sort(A,1,n)$
• 过程：$merge\_sort(A,low,high)$
• $1.iflow<highthen$
• $2.mid\leftarrow \lfloor (low+high)/2\rfloor$
• $3.merge\_sort(A,low,mid)$
• $4.merge\_sort(A,mid+1,high)$
• $5.merge(A,low,mid,high)$
• $6.endif$

————————————————————————————————

复杂度分析

显然，上述算法中的基本运算是元素比较，换句话说，我们可以认为运行时间与由算法执行的元素比较次数是成正比的。因此现在的主要工作，就是计算出合并排序算法对数组 $A[1\dots n]$ 排序时，总计执行的元素比较次数 $C(n)$。首先，为了简便计算，我们不失一般性地假设 $n=2^k,k\in N$。
再回到伪代码，
当 $n=1$ 时，算法不执行任何元素比较操作，即 $C(1)=0$；
当 $n⩾2$ 时，算法执行了步骤 $2\sim 5$，步骤 $3$ 和 $4$ 执行的元素比较操作都是 $C(\frac{n}{2})$ 次，根据合并操作算法的定义，易知合并两个子数组需要执行元素比较操作 $\frac{2}{n}\sim n-1$ 次。因此得到如下两个递推关系式：

• 最好情况：$C(n)=\{\begin{array}{l}0ifn=1\\ \\ 2C(\frac{n}{2})+\frac{n}{2}ifn⩾2\end{array}$，易得 $C(n)=\frac{n\log n}{2}$

• 最坏情况：$C(n)=\{\begin{array}{l}0ifn=1\\ \\ 2C(\frac{n}{2})+n-1ifn⩾2\end{array}$，展开得
  $C(n)=2C(\frac{n}{2})+n-1$
  $=2(2C(\frac{n}{2^2})+\frac{n}{2}-1)+n-1$
  $=2^{2}C(\frac{n}{2^2})+n-2+n-1$
  $=\cdots =2^{k}C(\frac{n}{2^k})+kn-2^{k-1}-2^{k-2}-\cdots -2-1$
  $=2^{k}C(1)+kn-{\sum }_{i=0}^{k-1}{2}^i$
  $=0+kn-(2^k-1)$
  $=n\log n-n+1$

综上，若 $n$ 是任意正整数，则有合并排序算法执行的元素比较次数为
$C(n)=\{\begin{array}{l}0ifn=1\\ \\ C(\lfloor n/2\rfloor )+C(\lceil n/2\rceil )+bnifn⩾2\end{array}$，其中 $b$ 为非负常数，易知解为 $C(n)=\Theta (n\log n)$，
进一步得到，算法的实际复杂度为 $T(n)=n\log n$。

实现

$C$++

void merge(int A[], int m, int p, int q, int r){
	int B[m];
	int s = p, t = q + 1, k = p;
	while((s <= q) && (t <= r)){
		if(A[s] <= A[t]) B[k] = A[s++];
		else B[k] = A[t++];
		k++;
	}
	if( s == q + 1){
		for(int i=0; i<=r-k; i++) B[k+i] = A[t+i];
	}else{
		for(int i=0; i<=r-k; i++) B[k+i] = A[s+i];
	}
	for(int i=0; i<=r-p; i++) A[p+i] = B[p+i];
}
void merge_sort(int A[], int m, int low, int high){
	if(low < high){
		int mid = (low + high) / 2;
		merge_sort(A, m, low, mid);
		merge_sort(A, m, mid+1, high);
		merge(A, m, low, mid, high);
	}
}

$Python$

def merge(A, m, p, q, r):
	B = [];
	for i in range(0, m):
		B.append(0)

	s, t, k = p, q+1, p;
	while (s <= q) and (t <= r):
		if A[s] <= A[t]:
			B[k] = A[s]
			s += 1
		else:
			B[k] = A[t]
			t += 1
		k += 1

	if s == q+1:
		for i in range(0, r-k+1):
			B[k+i] = A[t+i]
	else:
		for i in range(0, r-k+1):
			B[k+i] = A[s+i]

	for i in range(0, r-p+1):
		A[p+i] = B[p+i]

def merge_sort(A, m, low, high):
	if low < high:
		mid = int((low + high) / 2)
		merge_sort(A, m, low, mid)
		merge_sort(A, m, mid+1, high)
		merge(A, m, low, mid, high)

	return A

$Java$

public static void merge(int[] A, int m, int p, int q, int r){
	int[] B = new int[m];
	int s = p, t = q + 1, k = p;
	while((s <= q) && (t <= r)){
		if(A[s] <= A[t]) B[k] = A[s++];
		else B[k] = A[t++];
		k++;
	}
	if( s == q + 1){
		for(int i=0; i<=r-k; i++) B[k+i] = A[t+i];
	}else{
		for(int i=0; i<=r-k; i++) B[k+i] = A[s+i];
	}
	for(int i=0; i<=r-p; i++) A[p+i] = B[p+i];
}

public static void mergeSort(int[] A, int m, int low, int high){
	if(low < high){
		int mid = (low + high) / 2;
		mergeSort(A, m, low, mid);
		mergeSort(A, m, mid+1, high);
		merge(A, m, low, mid, high);
	}
}

表格分割线

6. 希尔排序

算法原理

希尔排序算法实际上是直接插入排序算法的升级版。它的主要思路就是把序列中的元素按照下标的一定增量进行分组，然后再对每个分组执行直接插入排序算法。随着增量逐渐减少，每个分组包含的元素值也随之增加，当增量减至 $1$ 时，所有元素都被分到一组之中，算法终止。下面我们以数组为例来深入学习一下算法的设计思路：
设 $A[1\dots n]$ 为一实数数组；

• 首先，我们选择一个小于 $n$ 的整数 $d_1$ 作为第一个增量，结合数组元素的下标索引将所有元素完成分组，分组标准即所有距离为 $d_1$ 的倍数的元素放在同一组中（实际上就是将数组下标划分成公差为 $d_1$，首项不同的等差数列）；
• 其次，针对各组分别进行直接插入排序；
• 再次，取第二个增量 $d_2<d_1$，重复以上的分组和排序操作；
• 最终，直至所取的增量 $d_t=1,d_t<d_{t-1}<\cdots <d_2<d_1$，即所有元素放在同一组中，执行直接插入排序算法，排序完成。

增量的选取一半先选择数组大小的一半，以后依次减半，直至增量为 $1$。下面我们再根据一个具体的例子来消化一下上述算法：

待排序数组	A [ 1 … n ] = { 49 ,   38 ,   65 ,   97 ,   76 ,   13 ,   27 ,   48 ,   55 ,   4 } A[1dots n]={49,space38,space65,space 97,space76,space13,space27,space48,space55,space4} A[1…n]={49, 38, 65, 97, 76, 13, 27, 48, 55, 4}
$d_1=5$，一趟分组	A [ 1 … n ] = { A[1dots n]={ A[1…n]={ $49$ , $38$ , $65$ , $97$, $76$ , $13$ , $27$ , $48$ , $55$ , $4$ $\}$
一趟排序	A [ 1 … n ] = { A[1dots n]={ A[1…n]={ $13$ , $27$ , $48$ , $55$ , $4$ , $49$ , $38$ , $65$ , $97$, $76$ $\}$
$d_2=2$，二趟分组	A [ 1 … n ] = { A[1dots n]={ A[1…n]={ $13$ , $27$ , $48$ , $55$ , $4$ , $49$ , $38$ , $65$ , $97$ , $76$ $\}$
二趟排序	A [ 1 … n ] = { A[1dots n]={ A[1…n]={ $4$ , $27$ , $13$ , $49$ , $38$ , $55$ , $48$ , $65$ , $97$ , $76$ $\}$
$d_3=1$，三趟分组	A [ 1 … n ] = { 4 ,   27 ,   13 ,   49 ,   38 ,   55 ,   48 ,   65 ,   97 ,   76 } A[1dots n]={4,space27,space13,space 49,space38,space55,space48,space65,space97,space76} A[1…n]={4, 27, 13, 49, 38, 55, 48, 65, 97, 76}
三趟排序，排序完毕	A [ 1 … n ] = { 4 ,   13 ,   27 ,   38 ,   48 ,   49 ,   55 ,   65 ,   76 ,   97 } A[1dots n]={4,space13,space27,space 38,space48,space49,space55,space65,space76,space97} A[1…n]={4, 13, 27, 38, 48, 49, 55, 65, 76, 97}

伪代码如下：
—————————-——$shell\_sort$——————————————

• 输入：待排序数组 $A[0\dots n-1]$，数组长度 $n$
• 输出：按非降序排列的数组 $A[0\dots n-1]$
• $1.flag\leftarrow \lfloor n/2\rfloor$
• $2.whileflag>0$
• $3.fori\leftarrow flagton-1$
• $4.t\leftarrow A[i];j\leftarrow i-flag$
• $5.while(j⩾0andt<A[j)$
• $6.A[j+flag]\leftarrow A[j]$
• $7.j\leftarrow j-flag$
• $8.endwhile$
• $9.A[j+flag]\leftarrow t$
• $10.endfor$
• $11.flag\leftarrow \lfloor flag/2\rfloor$
• $12.endwhile$

————————————————————————————————

复杂度分析

希尔排序算法不需要大量的辅助空间，和归并排序算法一样易于实现。事实上，希尔排序是基于插入排序的一种算法，主要是在直接插入排序算法的基础上增加了一个新的特性，进而提高了效率，因此结合之前插入排序算法时间复杂度的计算，我们很容易得到希尔排序算法的时间复杂度为 $O(n^{\frac{3}{2}})$。
可见，希尔排序在中等大小规模的输入中表现良好，对于规模非常大的输入就不是最优选择了。此外，希尔排序在最坏情况下的执行效率和平均情况相差不大。因此，许多程序员在开始排序工作时，都会先试试希尔排序，如果表现不好，再更改为快速排序这样更高级的排序算法（一是因为它比较难写，二则是因为快速排序算法在最坏情况下效率极低）。

实现

$C$++

void shell_sort(int A[], int n){
	int flag = n / 2;
	while(flag > 0){
		for(int i=flag; i<n; i++){
			int t = A[i], j = i - flag;
			while(j >= 0 && t < A[j]){
				A[j+flag] = A[j];
				j -= flag;
			}
			A[j+flag] = t;
		}
		flag /= 2;
	}
}

$Python$

def shell_sort(A, n):
	flag = n // 2
	while flag > 0:
		for i in range(flag, n):
			t, j = A[i], i - flag
			while j >= 0 and t < A[j]:
				A[j+flag] = A[j]
				j -= flag
			A[j+flag]= t
		flag = flag // 2

	return A

$Java$

public static void shellSort(int[] A, int n){
	int flag = n / 2;
	while(flag > 0){
		for(int i=flag; i<n; i++){
			int t = A[i], j = i - flag;
			while(j >= 0 && t < A[j]){
				A[j+flag] = A[j];
				j -= flag;
			}
			A[j+flag] = t;
		}
		flag /= 2;
	}
}

最后

以上就是霸气长颈鹿为你收集整理的排序算法（6种基础排序算法）排序算法的全部内容，希望文章能够帮你解决排序算法（6种基础排序算法）排序算法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。