一、什么是排序算法

1.1、排序定义

对一序列对象根据某个关键字进行排序。

1.2、排序术语

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
内排序：所有排序操作都在内存中完成；
外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
时间复杂度： 一个算法执行所耗费的时间。
空间复杂度：运行完一个程序所需内存的大小。

1.3、算法总结


​


（注意：n指数据规模；k指“桶”的个数；In-place指占用常数内存，不占用额外内存；Out-place指占用额外内存）

1.4、算法分类


​


1.5、比较和非比较的区别

常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序。在排序的最终结果里，元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较，才能确定自己的位置。在冒泡排序之类的排序中，问题规模为n，又因为需要比较n次，所以平均时间复杂度为O(n²)。在归并排序、快速排序之类的排序中，问题规模通过分治法消减为logN次，所以时间复杂度平均O(nlogn)。比较排序的优势是，适用于各种规模的数据，也不在乎数据的分布，都能进行排序。可以说，比较排序适用于一切需要排序的情况。计数排序、基数排序、桶排序则属于非比较排序。非比较排序是通过确定每个元素之前，应该有多少个元素来排序。针对数组arr，计算arr[i]之前有多少个元素，则唯一确定了arr[i]在排序后数组中的位置。非比较排序只要确定每个元素之前的已有的元素个数即可，所有一次遍历即可解决。算法时间复杂度O(n)。非比较排序时间复杂度底，但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。

二、冒泡排序（Bubble Sort）

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 

2.1、算法描述

比较相邻的元素。如果第一个比第二个大，就交换它们两个；
	
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
	
针对所有的元素重复以上的步骤，除了最后一个；
	
重复步骤1~3，直到排序完成。
2.2、动图演示


​


2.3、代码实现


/**
 * 冒泡排序
 *
 * @param array
 * @return
 */
public static int[] bubbleSort(int[] array) {
	if (array.length == 0)
		return array;
	for (int i = 0; i < array.length; i++)
		for (int j = 0; j < array.length - 1 - i; j++)
			if (array[j + 1] < array[j]) {
				int temp = array[j + 1];
				array[j + 1] = array[j];
				array[j] = temp;
			}
	return array;
}


2.4、算法分析

最佳情况：T(n) = O(n)   最差情况：T(n) = O(n2)   平均情况：T(n) = O(n2)

三、选择排序（Selection Sort）

表现最稳定的排序算法之一，因为无论什么数据进去都是O(n2)的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧。选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。 

3.1、算法描述

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

初始状态：无序区为R[1..n]，有序区为空；
	
第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
	
n-1趟结束，数组有序化了。
3.2、动图演示


​


3.3、代码实现


/**
 * 选择排序
 * @param array
 * @return
 */
public static int[] selectionSort(int[] array) {
	if (array.length == 0)
		return array;
	for (int i = 0; i < array.length; i++) {
		int minIndex = i;
		for (int j = i; j < array.length; j++) {
			if (array[j] < array[minIndex]) //找到最小的数
				minIndex = j; //将最小数的索引保存
		}
		int temp = array[minIndex];
		array[minIndex] = array[i];
		array[i] = temp;
	}
	return array;
}


3.4、算法分析

最佳情况：T(n) = O(n2)  最差情况：T(n) = O(n2)  平均情况：T(n) = O(n2)

四、插入排序（Insertion Sort）

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

4.1、算法描述

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

从第一个元素开始，该元素可以认为已经被排序；
	
取出下一个元素，在已经排序的元素序列中从后向前扫描；
	
如果该元素（已排序）大于新元素，将该元素移到下一位置；
	
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
	
将新元素插入到该位置后；
	
重复步骤2~5。
4.2、动图演示


​


4.3、代码实现


/**
 * 插入排序
 * @param array
 * @return
 */
public static int[] insertionSort(int[] array) {
	if (array.length == 0)
		return array;
	int current;
	for (int i = 0; i < array.length - 1; i++) {
		current = array[i + 1];
		int preIndex = i;
		while (preIndex >= 0 && current < array[preIndex]) {
			array[preIndex + 1] = array[preIndex];
			preIndex--;
		}
		array[preIndex + 1] = current;
	}
	return array;
}


4.4、算法分析

最佳情况：T(n) = O(n)   最坏情况：T(n) = O(n2)   平均情况：T(n) = O(n2)

五、希尔排序（Shell Sort）

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。希尔排序是把记录按下表的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

5.1、算法描述

我们来看下希尔排序的基本步骤，在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2...1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
	
按增量序列个数k，对序列进行k 趟排序；
	
每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
5.2、过程演示


​


5.3、代码实现


/**
 * 希尔排序
 *
 * @param array
 * @return
 */
public static int[] ShellSort(int[] array) {
	int len = array.length;
	int temp, gap = len / 2;
	while (gap > 0) {
		for (int i = gap; i < len; i++) {
			temp = array[i];
			int preIndex = i - gap;
			while (preIndex >= 0 && array[preIndex] > temp) {
				array[preIndex + gap] = array[preIndex];
				preIndex -= gap;
			}
			array[preIndex + gap] = temp;
		}
		gap /= 2;
	}
	return array;
}


5.4、算法分析

最佳情况：T(n) = O(nlog2 n)  最坏情况：T(n) = O(nlog2 n)  平均情况：T(n) =O(nlog2n)　

六、归并排序（Merge Sort）

和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n log n）的时间复杂度。代价是需要额外的内存空间。归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。 

6.1、算法描述

把长度为n的输入序列分成两个长度为n/2的子序列；
	
对这两个子序列分别采用归并排序；
	
将两个排序好的子序列合并成一个最终的排序序列。
6.2、动图演示


​


6.3、代码实现


/**
 * 归并排序
 *
 * @param array
 * @return
 */
public static int[] MergeSort(int[] array) {
	if (array.length < 2) return array;
	int mid = array.length / 2;
	int[] left = Arrays.copyOfRange(array, 0, mid);
	int[] right = Arrays.copyOfRange(array, mid, array.length);
	return merge(MergeSort(left), MergeSort(right));
}
/**
 * 归并排序——将两段排序好的数组结合成一个排序数组
 *
 * @param left
 * @param right
 * @return
 */
public static int[] merge(int[] left, int[] right) {
	int[] result = new int[left.length + right.length];
	for (int index = 0, i = 0, j = 0; index < result.length; index++) {
		if (i >= left.length)
			result[index] = right[j++];
		else if (j >= right.length)
			result[index] = left[i++];
		else if (left[i] > right[j])
			result[index] = right[j++];
		else
			result[index] = left[i++];
	}
	return result;
}


6.4、算法分析

最佳情况：T(n) = O(n)  最差情况：T(n) = O(nlogn)  平均情况：T(n) = O(nlogn)

七、快速排序（Quick Sort）

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

7.1、算法描述

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

从数列中挑出一个元素，称为 “基准”（pivot）；
	
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
	
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
7.2、动图演示


​


7.3、代码实现



/**
 * 快速排序方法
 * @param array
 * @param start
 * @param end
 * @return
 */
public static int[] QuickSort(int[] array, int start, int end) {
	if (array.length < 1 || start < 0 || end >= array.length || start > end) return null;
	int smallIndex = partition(array, start, end);
	if (smallIndex > start)
		QuickSort(array, start, smallIndex - 1);
	if (smallIndex < end)
		QuickSort(array, smallIndex + 1, end);
	return array;
}
/**
 * 快速排序算法——partition
 * @param array
 * @param start
 * @param end
 * @return
 */
public static int partition(int[] array, int start, int end) {
	int pivot = (int) (start + Math.random() * (end - start + 1));
	int smallIndex = start - 1;
	swap(array, pivot, end);
	for (int i = start; i <= end; i++)
		if (array[i] <= array[end]) {
			smallIndex++;
			if (i > smallIndex)
				swap(array, i, smallIndex);
		}
	return smallIndex;
}

/**
 * 交换数组内两个元素
 * @param array
 * @param i
 * @param j
 */
public static void swap(int[] array, int i, int j) {
	int temp = array[i];
	array[i] = array[j];
	array[j] = temp;
}


 



​7.4、算法分析

最佳情况：T(n) = O(nlogn)   最差情况：T(n) = O(n2)   平均情况：T(n) = O(nlogn)　

八、堆排序（Heap Sort）

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

8.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，则整个排序过程完成。
8.2、动图演示



 

8.3、代码实现

//声明全局变量，用于记录数组array的长度；
static int len;
/**
 * 堆排序算法
 *
 * @param array
 * @return
 */
public static int[] HeapSort(int[] array) {
	len = array.length;
	if (len < 1) return array;
	//1.构建一个最大堆
	buildMaxHeap(array);
	//2.循环将堆首位（最大值）与末位交换，然后在重新调整最大堆
	while (len > 0) {
		swap(array, 0, len - 1);
		len--;
		adjustHeap(array, 0);
	}
	return array;
}
/**
 * 建立最大堆
 *
 * @param array
 */
public static void buildMaxHeap(int[] array) {
	//从最后一个非叶子节点开始向上构造最大堆
	for (int i = (len/2 - 1); i >= 0; i--) { //感谢 @让我发会呆 网友的提醒，此处应该为 i = (len/2 - 1) 
		adjustHeap(array, i);
	}
}
/**
 * 调整使之成为最大堆
 *
 * @param array
 * @param i
 */
public static void adjustHeap(int[] array, int i) {
	int maxIndex = i;
	//如果有左子树，且左子树大于父节点，则将最大指针指向左子树
	if (i * 2 < len && array[i * 2] > array[maxIndex])
		maxIndex = i * 2;
	//如果有右子树，且右子树大于父节点，则将最大指针指向右子树
	if (i * 2 + 1 < len && array[i * 2 + 1] > array[maxIndex])
		maxIndex = i * 2 + 1;
	//如果父节点不是最大值，则将父节点与最大值交换，并且递归调整与父节点交换的位置。
	if (maxIndex != i) {
		swap(array, maxIndex, i);
		adjustHeap(array, maxIndex);
	}
}

8.4、算法分析

最佳情况：T(n) = O(nlogn) 最差情况：T(n) = O(nlogn) 平均情况：T(n) = O(nlogn)

九、计数排序（Counting Sort）

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。

9.1、算法描述

找出待排序的数组中最大和最小的元素；
	
统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
	
对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
	
反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
9.2、动图演示



9.3、代码实现

/**
 * 计数排序
 *
 * @param array
 * @return
 */
public static int[] CountingSort(int[] array) {
	if (array.length == 0) return array;
	int bias, min = array[0], max = array[0];
	for (int i = 1; i < array.length; i++) {
		if (array[i] > max)
			max = array[i];
		if (array[i] < min)
			min = array[i];
	}
	bias = 0 - min;
	int[] bucket = new int[max - min + 1];
	Arrays.fill(bucket, 0);
	for (int i = 0; i < array.length; i++) {
		bucket[array[i] + bias]++;
	}
	int index = 0, i = 0;
	while (index < array.length) {
		if (bucket[i] != 0) {
			array[index] = i - bias;
			bucket[i]--;
			index++;
		} else
			i++;
	}
	return array;
}

9.4、算法分析

当输入的元素是n 个0到k之间的整数时，它的运行时间是 O(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。最佳情况：T(n) = O(n+k)  最差情况：T(n) = O(n+k)  平均情况：T(n) = O(n+k)

十、桶排序（Bucket Sort）

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排。

10.1、算法描述

人为设置一个BucketSize，作为每个桶所能放置多少个不同数值（例如当BucketSize==5时，该桶可以存放｛1,2,3,4,5｝这几种数字，但是容量不限，即可以存放100个3）；
	
遍历输入数据，并且把数据一个一个放到对应的桶里去；
	
对每个不是空的桶进行排序，可以使用其它排序方法，也可以递归使用桶排序；
	
从不是空的桶里把排好序的数据拼接起来。 
注意，如果递归使用桶排序为各个桶排序，则当桶数量为1时要手动减小BucketSize增加下一循环桶的数量，否则会陷入死循环，导致内存溢出。

10.2、图片演示



10.3、代码实现

/**
 * 桶排序
 * 
 * @param array
 * @param bucketSize
 * @return
 */
public static ArrayList<Integer> BucketSort(ArrayList<Integer> array, int bucketSize) {
	if (array == null || array.size() < 2)
		return array;
	int max = array.get(0), min = array.get(0);
	// 找到最大值最小值
	for (int i = 0; i < array.size(); i++) {
		if (array.get(i) > max)
			max = array.get(i);
		if (array.get(i) < min)
			min = array.get(i);
	}
	int bucketCount = (max - min) / bucketSize + 1;
	ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount);
	ArrayList<Integer> resultArr = new ArrayList<>();
	for (int i = 0; i < bucketCount; i++) {
		bucketArr.add(new ArrayList<Integer>());
	}
	for (int i = 0; i < array.size(); i++) {
		bucketArr.get((array.get(i) - min) / bucketSize).add(array.get(i));
	}
	for (int i = 0; i < bucketCount; i++) {
		if (bucketSize == 1) { // 如果带排序数组中有重复数字时  感谢 @见风任然是风 朋友指出错误
			for (int j = 0; j < bucketArr.get(i).size(); j++)
				resultArr.add(bucketArr.get(i).get(j));
		} else {
			if (bucketCount == 1)
				bucketSize--;
			ArrayList<Integer> temp = BucketSort(bucketArr.get(i), bucketSize);
			for (int j = 0; j < temp.size(); j++)
				resultArr.add(temp.get(j));
		}
	}
	return resultArr;
}

10.4、算法分析

桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。 最佳情况：T(n) = O(n+k)   最差情况：T(n) = O(n+k)   平均情况：T(n) = O(n2)　　

十一、基数排序（Radix Sort）

基数排序也是非比较的排序算法，对每一位进行排序，从最低位开始排序，复杂度为O(kn),为数组长度，k为数组中的数的最大的位数；基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。

11.1、算法描述

取得数组中的最大数，并取得位数；
	
arr为原始数组，从最低位开始取每个位组成radix数组；
	
对radix进行计数排序（利用计数排序适用于小范围数的特点）；
11.2、动图演示



11.3、代码实现

/**
 * 基数排序
 * @param array
 * @return
 */
public static int[] RadixSort(int[] array) {
	if (array == null || array.length < 2)
		return array;
	// 1.先算出最大数的位数；
	int max = array[0];
	for (int i = 1; i < array.length; i++) {
		max = Math.max(max, array[i]);
	}
	int maxDigit = 0;
	while (max != 0) {
		max /= 10;
		maxDigit++;
	}
	int mod = 10, div = 1;
	ArrayList<ArrayList<Integer>> bucketList = new ArrayList<ArrayList<Integer>>();
	for (int i = 0; i < 10; i++)
		bucketList.add(new ArrayList<Integer>());
	for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
		for (int j = 0; j < array.length; j++) {
			int num = (array[j] % mod) / div;
			bucketList.get(num).add(array[j]);
		}
		int index = 0;
		for (int j = 0; j < bucketList.size(); j++) {
			for (int k = 0; k < bucketList.get(j).size(); k++)
				array[index++] = bucketList.get(j).get(k);
			bucketList.get(j).clear();
		}
	}
	return array;
}

11.4、算法分析

最佳情况：T(n) = O(n * k)   最差情况：T(n) = O(n * k)   平均情况：T(n) = O(n * k)。基数排序有两种方法：MSD 从高位开始进行排序 LSD 从低位开始进行排序 。基数排序 vs 计数排序 vs 桶排序。这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

基数排序：根据键值的每位数字来分配桶
	
计数排序：每个桶只存储单一键值
	
桶排序：每个桶存储一定范围的数值

阅读此文推荐：前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。

概述

排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。

我们这里说说八大排序就是内部排序。



    

    当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。

   快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；



 

1.插入排序—直接插入排序(Straight Insertion Sort)

基本思想:

将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。

要点：设立哨兵，作为临时存储和判断数组边界之用。

直接插入排序示例：



 

如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

算法的实现：

void print(int a[], int n ,int i){
	cout<<i <<":";
	for(int j= 0; j<8; j++){
		cout<<a[j] <<" ";
	}
	cout<<endl;
}


void InsertSort(int a[], int n)
{
	for(int i= 1; i<n; i++){
		if(a[i] < a[i-1]){               //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入
			int j= i-1;	
			int x = a[i];		 //复制为哨兵，即存储待排序元素
			a[i] = a[i-1];           //先后移一个元素
			while(x < a[j]){	 //查找在有序表的插入位置
				a[j+1] = a[j];
				j--;		 //元素后移
			}
			a[j+1] = x;		 //插入到正确位置
		}
		print(a,n,i);			//打印每趟排序的结果
	}
	
}

int main(){
	int a[8] = {3,1,5,7,2,4,9,6};
	InsertSort(a,8);
	print(a,8,8);
}


 

效率：

 

时间复杂度：O（n^2）.

其他的插入排序有二分插入排序，2-路插入排序。

 

 2. 插入排序—希尔排序（Shell`s Sort）

希尔排序是1959 年由D.L.Shell 提出来的，相对直接排序有较大的改进。希尔排序又叫缩小增量排序

基本思想：

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

操作方法：

选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
	
按增量序列个数k，对序列进行k 趟排序；
	
每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
希尔排序的示例：shell排序的排序过程

假设待排序文件有10个记录，其关键字分别是：49，38，65，97，76，13，27，49，55，04。

增量系列的取值依次为：5，3，1



 

算法实现：

我们简单处理增量序列：增量序列d = {n/2 ,n/4, n/8 .....1} n为要排序数的个数

即：先将要排序的一组记录按某个增量d（n/2,n为要排序数的个数）分成若干组子序列，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。继续不断缩小增量直至为1，最后使用直接插入排序完成排序。

void print(int a[], int n ,int i){
	cout<<i <<":";
	for(int j= 0; j<8; j++){
		cout<<a[j] <<" ";
	}
	cout<<endl;
}
/**
 * 直接插入排序的一般形式
 *
 * @param int dk 缩小增量，如果是直接插入排序，dk=1
 *
 */

void ShellInsertSort(int a[], int n, int dk)
{
	for(int i= dk; i<n; ++i){
		if(a[i] < a[i-dk]){			//若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入
			int j = i-dk;	
			int x = a[i];			//复制为哨兵，即存储待排序元素
			a[i] = a[i-dk];			//首先后移一个元素
			while(x < a[j]){		//查找在有序表的插入位置
				a[j+dk] = a[j];
				j -= dk;			 //元素后移
			}
			a[j+dk] = x;			//插入到正确位置
		}
		print(a, n,i );
	}
	
}

/**
 * 先按增量d（n/2,n为要排序数的个数进行希尔排序
 *
 */
void shellSort(int a[], int n){

	int dk = n/2;
	while( dk >= 1  ){
		ShellInsertSort(a, n, dk);
		dk = dk/2;
	}
}
int main(){
	int a[8] = {3,1,5,7,2,4,9,6};
	//ShellInsertSort(a,8,1); //直接插入排序
	shellSort(a,8);			  //希尔插入排序
	print(a,8,8);
}


 

希尔排序时效分析很难，关键码的比较次数与记录移动次数依赖于增量因子序列d的选取，特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没有人给出选取最好的增量因子序列的方法。增量因子序列可以有各种取法，有取奇数的，也有取质数的，但需要注意：增量因子中除1 外没有公因子，且最后一个增量因子必须为1。希尔排序方法是一个不稳定的排序方法。

 

3. 选择排序—简单选择排序（Simple Selection Sort）

基本思想：

在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。

简单选择排序的示例：

 

操作方法：

第一趟，从n 个记录中找出关键码最小的记录与第一个记录交换；

第二趟，从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录交换；

以此类推.....

第i 趟，则从第i 个记录开始的n-i+1 个记录中选出关键码最小的记录与第i 个记录交换，

直到整个序列按关键码有序。


 

算法实现：

void print(int a[], int n ,int i){
	cout<<"第"<<i+1 <<"趟 : ";
	for(int j= 0; j<8; j++){
		cout<<a[j] <<"  ";
	}
	cout<<endl;
}
/**
 * 数组的最小值
 *
 * @return int 数组的键值
 */
int SelectMinKey(int a[], int n, int i)
{
	int k = i;
	for(int j=i+1 ;j< n; ++j) {
		if(a[k] > a[j]) k = j;
	}
	return k;
}

/**
 * 选择排序
 *
 */
void selectSort(int a[], int n){
	int key, tmp;
	for(int i = 0; i< n; ++i) {
		key = SelectMinKey(a, n,i);           //选择最小的元素
		if(key != i){
			tmp = a[i];  a[i] = a[key]; a[key] = tmp; //最小元素与第i位置元素互换
		}
		print(a,  n , i);
	}
}
int main(){
	int a[8] = {3,1,5,7,2,4,9,6};
	cout<<"初始值：";
	for(int j= 0; j<8; j++){
		cout<<a[j] <<"  ";
	}
	cout<<endl<<endl;
	selectSort(a, 8);
	print(a,8,8);
}


 

 简单选择排序的改进——二元选择排序

 

简单选择排序，每趟循环只能确定一个元素排序后的定位。我们可以考虑改进为每趟循环确定两个元素（当前趟最大和最小记录）的位置,从而减少排序所需的循环次数。改进后对n个数据进行排序，最多只需进行[n/2]趟循环即可。具体实现如下：

/** 这是伪函数, 逻辑判断不严谨
void selectSort(int r[],int n) {
	int i ,j , min ,max, tmp;
	for (i=1 ;i <= n/2;i++) {  
		// 做不超过n/2趟选择排序 
		min = i; max = i ; //分别记录最大和最小关键字记录位置
		for (j= i+1; j<= n-i; j++) {
			if (r[j] > r[max]) { 
				max = j ; continue ; 
			}  
			if (r[j]< r[min]) { 
				min = j ; 
			}   
	  }  
	  //该交换操作还可分情况讨论以提高效率
	  tmp = r[i-1]; r[i-1] = r[min]; r[min] = tmp;
	  tmp = r[n-i]; r[n-i] = r[max]; r[max] = tmp; 
 
	} 
}
 */
void selectSort(int a[],int len) {
        int i,j,min,max,tmp;  
        for(i=0; i<len/2; i++){  // 做不超过n/2趟选择排序 
            min = max = i;  
            for(j=i+1; j<=len-1-i; j++){  
				//分别记录最大和最小关键字记录位置
                if(a[j] > a[max]){  
                    max = j;  
                    continue;  
                }  
                if(a[j] < a[min]){  
                    min = j;  
                }  
            }  
			//该交换操作还可分情况讨论以提高效率
            if(min != i){//当第一个为min值，不用交换  
                tmp=a[min];  a[min]=a[i];  a[i]=tmp;  
            }  
            if(min == len-1-i && max == i)//当第一个为max值，同时最后一个为min值，不再需要下面操作  
                continue;  
            if(max == i)//当第一个为max值，则交换后min的位置为max值  
                max = min;  
            if(max != len-1-i){//当最后一个为max值，不用交换  
                tmp=a[max];  a[max]=a[len-1-i];  a[len-1-i]=tmp;  
            }
			print(a,len, i);			
        }  
 }

 

4. 选择排序—堆排序（Heap Sort）

堆排序是一种树形选择排序，是对直接选择排序的有效改进。

基本思想：

堆的定义如下：具有n个元素的序列（k1,k2,...,kn),当且仅当满足



时称之为堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最小项（小顶堆）。

若以一维数组存储一个堆，则堆对应一棵完全二叉树，且所有非叶结点的值均不大于(或不小于)其子女的值，根结点（堆顶元素）的值是最小(或最大)的。如：

（a）大顶堆序列：（96, 83,27,38,11,09)

  (b)  小顶堆序列：（12，36，24，85，47，30，53，91）



初始时把要排序的n个数的序列看作是一棵顺序存储的二叉树（一维数组存储二叉树），调整它们的存储序，使之成为一个堆，将堆顶元素输出，得到n 个元素中最小(或最大)的元素，这时堆的根节点的数最小（或者最大）。然后对前面(n-1)个元素重新调整使之成为堆，输出堆顶元素，得到n 个元素中次小(或次大)的元素。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。称这个过程为堆排序。

因此，实现堆排序需解决两个问题：

1. 如何将n 个待排序的数建成堆；

2. 输出堆顶元素后，怎样调整剩余n-1 个元素，使其成为一个新堆。


首先讨论第二个问题：输出堆顶元素后，对剩余n-1元素重新建成堆的调整过程。

调整小顶堆的方法：

1）设有m 个元素的堆，输出堆顶元素后，剩下m-1 个元素。将堆底元素送入堆顶（（最后一个元素与堆顶进行交换），堆被破坏，其原因仅是根结点不满足堆的性质。

2）将根结点与左、右子树中较小元素的进行交换。

3）若与左子树交换：如果左子树堆被破坏，即左子树的根结点不满足堆的性质，则重复方法 （2）.

4）若与右子树交换，如果右子树堆被破坏，即右子树的根结点不满足堆的性质。则重复方法 （2）.

5）继续对不满足堆性质的子树进行上述交换操作，直到叶子结点，堆被建成。

称这个自根结点到叶子结点的调整过程为筛选。如图：




再讨论对n 个元素初始建堆的过程。

建堆方法：对初始序列建堆的过程，就是一个反复进行筛选的过程。

1）n 个结点的完全二叉树，则最后一个结点是第个结点的子树。

2）筛选从第个结点为根的子树开始，该子树成为堆。

3）之后向前依次对各结点为根的子树进行筛选，使之成为堆，直到根结点。

如图建堆初始过程：无序序列：（49，38，65，97，76，13，27，49）



                             

 算法的实现：

从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。

void print(int a[], int n){
	for(int j= 0; j<n; j++){
		cout<<a[j] <<"  ";
	}
	cout<<endl;
}



/**
 * 已知H[s…m]除了H[s] 外均满足堆的定义
 * 调整H[s],使其成为大顶堆.即将对第s个结点为根的子树筛选, 
 *
 * @param H是待调整的堆数组
 * @param s是待调整的数组元素的位置
 * @param length是数组的长度
 *
 */
void HeapAdjust(int H[],int s, int length)
{
	int tmp  = H[s];
	int child = 2*s+1; //左孩子结点的位置。(i+1 为当前调整结点的右孩子结点的位置)
    while (child < length) {
		if(child+1 <length && H[child]<H[child+1]) { // 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点)
			++child ;
		}
		if(H[s]<H[child]) {  // 如果较大的子结点大于父结点
			H[s] = H[child]; // 那么把较大的子结点往上移动，替换它的父结点
			s = child;		 // 重新设置s ,即待调整的下一个结点的位置
			child = 2*s+1;
		}  else {			 // 如果当前待调整结点大于它的左右孩子，则不需要调整，直接退出
			 break;
		}
		H[s] = tmp;			// 当前待调整的结点放到比其大的孩子结点位置上
	}
	print(H,length);
}


/**
 * 初始堆进行调整
 * 将H[0..length-1]建成堆
 * 调整完之后第一个元素是序列的最小的元素
 */
void BuildingHeap(int H[], int length)
{ 
	//最后一个有孩子的节点的位置 i=  (length -1) / 2
	for (int i = (length -1) / 2 ; i >= 0; --i)
		HeapAdjust(H,i,length);
}
/**
 * 堆排序算法
 */
void HeapSort(int H[],int length)
{
    //初始堆
	BuildingHeap(H, length);
	//从最后一个元素开始对序列进行调整
	for (int i = length - 1; i > 0; --i)
	{
		//交换堆顶元素H[0]和堆中最后一个元素
		int temp = H[i]; H[i] = H[0]; H[0] = temp;
		//每次交换堆顶元素和堆中最后一个元素之后，都要对堆进行调整
		HeapAdjust(H,0,i);
  }
} 

int main(){
	int H[10] = {3,1,5,7,2,4,9,6,10,8};
	cout<<"初始值：";
	print(H,10);
	HeapSort(H,10);
	//selectSort(a, 8);
	cout<<"结果：";
	print(H,10);

}



 

分析:

设树深度为k，。从根到叶的筛选，元素比较次数至多2(k-1)次，交换记录至多k 次。所以，在建好堆后，排序过程中的筛选次数不超过下式： 

                                

而建堆时的比较次数不超过4n 次，因此堆排序最坏情况下，时间复杂度也为：O(nlogn )。

 

5. 交换排序—冒泡排序（Bubble Sort）

基本思想：

在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

冒泡排序的示例：

 

算法的实现：

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;
			}
		}
	}
}

 

冒泡排序算法的改进

对冒泡排序常见的改进方法是加入一标志性变量exchange，用于标志某一趟排序过程中是否有数据交换，如果进行某一趟排序时并没有进行数据交换，则说明数据已经按要求排列好，可立即结束排序，避免不必要的比较过程。本文再提供以下两种改进算法：

1．设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。

改进后算法如下:

void Bubble_1 ( int r[], int n) {
	int i= n -1;  //初始时,最后位置保持不变
	while ( i> 0) { 
		int pos= 0; //每趟开始时,无记录交换
		for (int j= 0; j< i; j++)
			if (r[j]> r[j+1]) {
				pos= j; //记录交换的位置 
				int tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp;
			} 
		i= pos; //为下一趟排序作准备
	 } 
}  


 

2．传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。

改进后的算法实现为:

void Bubble_2 ( int r[], int n){
	int low = 0; 
	int high= n -1; //设置变量的初始值
	int tmp,j;
	while (low < high) {
		for (j= low; j< high; ++j) //正向冒泡,找到最大者
			if (r[j]> r[j+1]) {
				tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp;
			} 
		--high;					//修改high值, 前移一位
		for ( j=high; j>low; --j) //反向冒泡,找到最小者
			if (r[j]<r[j-1]) {
				tmp = r[j]; r[j]=r[j-1];r[j-1]=tmp;
			}
		++low;					//修改low值,后移一位
	} 
} 

 

6. 交换排序—快速排序（Quick Sort）

基本思想：

1）选择一个基准元素,通常选择第一个元素或者最后一个元素,

2）通过一趟排序讲待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的 元素值比基准值大。

3）此时基准元素在其排好序后的正确位置

4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。

快速排序的示例：

（a）一趟排序的过程：



（b）排序的全过程



算法的实现：

 递归实现：

void print(int a[], int n){
	for(int j= 0; j<n; j++){
		cout<<a[j] <<"  ";
	}
	cout<<endl;
}

void swap(int *a, int *b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

int partition(int a[], int low, int high)
{
	int privotKey = a[low];								//基准元素
	while(low < high){								    //从表的两端交替地向中间扫描
		while(low < high  && a[high] >= privotKey) --high;  //从high 所指位置向前搜索，至多到low+1 位置。将比基准元素小的交换到低端
		swap(&a[low], &a[high]);
		while(low < high  && a[low] <= privotKey ) ++low;
		swap(&a[low], &a[high]);
	}
	print(a,10);
	return low;
}


void quickSort(int a[], int low, int high){
	if(low < high){
		int privotLoc = partition(a,  low,  high);  //将表一分为二
		quickSort(a,  low,  privotLoc -1);			//递归对低子表递归排序
		quickSort(a,   privotLoc + 1, high);		//递归对高子表递归排序
	}
}

int main(){
	int a[10] = {3,1,5,7,2,4,9,6,10,8};
	cout<<"初始值：";
	print(a,10);
	quickSort(a,0,9);
	cout<<"结果：";
	print(a,10);

}

 

分析：

快速排序是通常被认为在同数量级（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。为改进之，通常以“三者取中法”来选取基准记录，即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。


快速排序的改进

在本改进算法中,只对长度大于k的子序列递归调用快速排序,让原序列基本有序，然后再对整个基本有序序列用插入排序算法排序。实践证明，改进后的算法时间复杂度有所降低，且当k取值为 8 左右时,改进算法的性能最佳。算法思想如下：

void print(int a[], int n){
	for(int j= 0; j<n; j++){
		cout<<a[j] <<"  ";
	}
	cout<<endl;
}

void swap(int *a, int *b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

int partition(int a[], int low, int high)
{
	int privotKey = a[low];					//基准元素
	while(low < high){					//从表的两端交替地向中间扫描
		while(low < high  && a[high] >= privotKey) --high; //从high 所指位置向前搜索，至多到low+1 位置。将比基准元素小的交换到低端
		swap(&a[low], &a[high]);
		while(low < high  && a[low] <= privotKey ) ++low;
		swap(&a[low], &a[high]);
	}
	print(a,10);
	return low;
}


void qsort_improve(int r[ ],int low,int high, int k){
	if( high -low > k ) { //长度大于k时递归, k为指定的数
		int pivot = partition(r, low, high); // 调用的Partition算法保持不变
		qsort_improve(r, low, pivot - 1,k);
		qsort_improve(r, pivot + 1, high,k);
	} 
} 
void quickSort(int r[], int n, int k){
	qsort_improve(r,0,n,k);//先调用改进算法Qsort使之基本有序

	//再用插入排序对基本有序序列排序
	for(int i=1; i<=n;i ++){
		int tmp = r[i]; 
		int j=i-1;
		while(tmp < r[j]){
			r[j+1]=r[j]; j=j-1; 
		}
		r[j+1] = tmp;
	} 

} 



int main(){
	int a[10] = {3,1,5,7,2,4,9,6,10,8};
	cout<<"初始值：";
	print(a,10);
	quickSort(a,9,4);
	cout<<"结果：";
	print(a,10);

}

 

7. 归并排序（Merge Sort）

基本思想：

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

归并排序示例：

 

 

合并方法：

设r[i…n]由两个有序子表r[i…m]和r[m+1…n]组成，两个子表长度分别为n-i +1、n-m。

j=m+1；k=i；i=i; //置两个子表的起始下标及辅助数组的起始下标
	
若i>m 或j>n，转⑷ //其中一个子表已合并完，比较选取结束
	
//选取r[i]和r[j]较小的存入辅助数组rf

	如果r[i]<r[j]，rf[k]=r[i]； i++； k++； 转⑵

	否则，rf[k]=r[j]； j++； k++； 转⑵
	
//将尚未处理完的子表中元素存入rf

	如果i<=m，将r[i…m]存入rf[k…n] //前一子表非空

	如果j<=n ,  将r[j…n] 存入rf[k…n] //后一子表非空
	
合并结束。
//将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n]
void Merge(ElemType *r,ElemType *rf, int i, int m, int n)
{
	int j,k;
	for(j=m+1,k=i; i<=m && j <=n ; ++k){
		if(r[j] < r[i]) rf[k] = r[j++];
		else rf[k] = r[i++];
	}
	while(i <= m)  rf[k++] = r[i++];
	while(j <= n)  rf[k++] = r[j++];
}

 

归并的迭代算法

1 个元素的表总是有序的。所以对n 个元素的待排序列，每个元素可看成1 个有序子表。对子表两两合并生成n/2个子表，所得子表除最后一个子表长度可能为1 外，其余子表长度均为2。再进行两两合并，直到生成n 个元素按关键码有序的表。

void print(int a[], int n){
	for(int j= 0; j<n; j++){
		cout<<a[j] <<"  ";
	}
	cout<<endl;
}

//将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n]
void Merge(ElemType *r,ElemType *rf, int i, int m, int n)
{
	int j,k;
	for(j=m+1,k=i; i<=m && j <=n ; ++k){
		if(r[j] < r[i]) rf[k] = r[j++];
		else rf[k] = r[i++];
	}
	while(i <= m)  rf[k++] = r[i++];
	while(j <= n)  rf[k++] = r[j++];
	print(rf,n+1);
}

void MergeSort(ElemType *r, ElemType *rf, int lenght)
{ 
	int len = 1;
	ElemType *q = r ;
	ElemType *tmp ;
	while(len < lenght) {
		int s = len;
		len = 2 * s ;
		int i = 0;
		while(i+ len <lenght){
			Merge(q, rf,  i, i+ s-1, i+ len-1 ); //对等长的两个子表合并
			i = i+ len;
		}
		if(i + s < lenght){
			Merge(q, rf,  i, i+ s -1, lenght -1); //对不等长的两个子表合并
		}
		tmp = q; q = rf; rf = tmp; //交换q,rf，以保证下一趟归并时，仍从q 归并到rf
	}
}


int main(){
	int a[10] = {3,1,5,7,2,4,9,6,10,8};
	int b[10];
	MergeSort(a, b, 10);
	print(b,10);
	cout<<"结果：";
	print(a,10);

}

 

两路归并的递归算法

void MSort(ElemType *r, ElemType *rf,int s, int t)
{ 
	ElemType *rf2;
	if(s==t) r[s] = rf[s];
	else
	{ 
		int m=(s+t)/2;			/*平分*p 表*/
		MSort(r, rf2, s, m);		/*递归地将p[s…m]归并为有序的p2[s…m]*/
		MSort(r, rf2, m+1, t);		/*递归地将p[m+1…t]归并为有序的p2[m+1…t]*/
		Merge(rf2, rf, s, m+1,t);	/*将p2[s…m]和p2[m+1…t]归并到p1[s…t]*/
	}
}
void MergeSort_recursive(ElemType *r, ElemType *rf, int n)
{   /*对顺序表*p 作归并排序*/
	MSort(r, rf,0, n-1);
}

8. 桶排序/基数排序(Radix Sort)

说基数排序之前，我们先说桶排序：

基本思想：是将阵列分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响。

         简单来说，就是把数据分组，放在一个个的桶中，然后对每个桶里面的在进行排序。  

 

 例如要对大小为[1..1000]范围内的n个整数A[1..n]排序  

 首先，可以把桶设为大小为10的范围，具体而言，设集合B[1]存储[1..10]的整数，集合B[2]存储   (10..20]的整数，……集合B[i]存储(   (i-1)*10,   i*10]的整数，i   =   1,2,..100。总共有  100个桶。  

  然后，对A[1..n]从头到尾扫描一遍，把每个A[i]放入对应的桶B[j]中。  再对这100个桶中每个桶里的数字排序，这时可用冒泡，选择，乃至快排，一般来说任  何排序法都可以。

  最后，依次输出每个桶里面的数字，且每个桶中的数字从小到大输出，这  样就得到所有数字排好序的一个序列了。  

  假设有n个数字，有m个桶，如果数字是平均分布的，则每个桶里面平均有n/m个数字。如果  

  对每个桶中的数字采用快速排序，那么整个算法的复杂度是  

  O(n   +   m   *   n/m*log(n/m))   =   O(n   +   nlogn   -   nlogm)  

  从上式看出，当m接近n的时候，桶排序复杂度接近O(n)  

  当然，以上复杂度的计算是基于输入的n个数字是平均分布这个假设的。这个假设是很强的  ，实际应用中效果并没有这么好。如果所有的数字都落在同一个桶中，那就退化成一般的排序了。  

        前面说的几大排序算法 ，大部分时间复杂度都是O（n2），也有部分排序算法时间复杂度是O(nlogn)。而桶式排序却能实现O（n）的时间复杂度。但桶排序的缺点是：

        1）首先是空间复杂度比较高，需要的额外开销大。排序有两个数组的空间开销，一个存放待排序数组，一个就是所谓的桶，比如待排序值是从0到m-1，那就需要m个桶，这个桶数组就要至少m个空间。

        2）其次待排序的元素都要在一定的范围内等等。

       桶式排序是一种分配排序。分配排序的特定是不需要进行关键码的比较，但前提是要知道待排序列的一些具体情况。

 

分配排序的基本思想：说白了就是进行多次的桶式排序。

基数排序过程无须比较关键字，而是通过“分配”和“收集”过程来实现排序。它们的时间复杂度可达到线性阶：O(n)。

实例:

扑克牌中52 张牌，可按花色和面值分成两个字段，其大小关系为：

花色： 梅花< 方块< 红心< 黑心  

面值： 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A

若对扑克牌按花色、面值进行升序排序，得到如下序列：





即两张牌，若花色不同，不论面值怎样，花色低的那张牌小于花色高的，只有在同花色情况下，大小关系才由面值的大小确定。这就是多关键码排序。

为得到排序结果，我们讨论两种排序方法。
方法1：先对花色排序，将其分为4 个组，即梅花组、方块组、红心组、黑心组。再对每个组分别按面值进行排序，最后，将4 个组连接起来即可。
方法2：先按13 个面值给出13 个编号组(2 号，3 号，...，A 号)，将牌按面值依次放入对应的编号组，分成13 堆。再按花色给出4 个编号组(梅花、方块、红心、黑心)，将2号组中牌取出分别放入对应花色组，再将3 号组中牌取出分别放入对应花色组，……，这样，4 个花色组中均按面值有序，然后，将4 个花色组依次连接起来即可。

设n 个元素的待排序列包含d 个关键码{k1，k2，…，kd}，则称序列对关键码{k1，k2，…，kd}有序是指：对于序列中任两个记录r[i]和r[j](1≤i≤j≤n)都满足下列有序关系：

                                                               

其中k1 称为最主位关键码，kd 称为最次位关键码     。

 

两种多关键码排序方法：

多关键码排序按照从最主位关键码到最次位关键码或从最次位到最主位关键码的顺序逐次排序，分两种方法：

最高位优先(Most Significant Digit first)法，简称MSD 法：

1）先按k1 排序分组，将序列分成若干子序列，同一组序列的记录中，关键码k1 相等。

2）再对各组按k2 排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd 对各子组排序后。

3）再将各组连接起来，便得到一个有序序列。扑克牌按花色、面值排序中介绍的方法一即是MSD 法。

最低位优先(Least Significant Digit first)法，简称LSD 法：

1) 先从kd 开始排序，再对kd-1进行排序，依次重复，直到按k1排序分组分成最小的子序列后。

2) 最后将各个子序列连接起来，便可得到一个有序的序列, 扑克牌按花色、面值排序中介绍的方法二即是LSD 法。

 

基于LSD方法的链式基数排序的基本思想

　　“多关键字排序”的思想实现“单关键字排序”。对数字型或字符型的单关键字，可以看作由多个数位或多个字符构成的多关键字，此时可以采用“分配-收集”的方法进行排序，这一过程称作基数排序法，其中每个数字或字符可能的取值个数称为基数。比如，扑克牌的花色基数为4，面值基数为13。在整理扑克牌时，既可以先按花色整理，也可以先按面值整理。按花色整理时，先按红、黑、方、花的顺序分成4摞（分配），再按此顺序再叠放在一起（收集），然后按面值的顺序分成13摞（分配），再按此顺序叠放在一起（收集），如此进行二次分配和收集即可将扑克牌排列有序。   

基数排序:

是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。

算法实现：

Void RadixSort(Node L[],length,maxradix)
{
   int m,n,k,lsp;
   k=1;m=1;
   int temp[10][length-1];
   Empty(temp); //清空临时空间
   while(k<maxradix) //遍历所有关键字
   {
     for(int i=0;i<length;i++) //分配过程
    {
       if(L[i]<m)
          Temp[0][n]=L[i];
       else
          Lsp=(L[i]/m)%10; //确定关键字
       Temp[lsp][n]=L[i];
       n++;
   }
   CollectElement(L,Temp); //收集
   n=0;
   m=m*10;
  k++;
 }
}

 

 

 

总结

各种排序的稳定性，时间复杂度和空间复杂度总结：



 我们比较时间复杂度函数的情况：



 

                             时间复杂度函数O(n)的增长情况



所以对n较大的排序记录。一般的选择都是时间复杂度为O(nlog2n)的排序方法。

 

时间复杂度来说：

(1)平方阶(O(n2))排序

　　各类简单排序:直接插入、直接选择和冒泡排序；

 (2)线性对数阶(O(nlog2n))排序

　　快速排序、堆排序和归并排序；

 (3)O(n1+§))排序,§是介于0和1之间的常数。

       希尔排序

(4)线性阶(O(n))排序

　　基数排序，此外还有桶、箱排序。

说明：

当原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至O（n）；

而快速排序则相反，当原表基本有序时，将蜕化为冒泡排序，时间复杂度提高为O（n2）；

原表是否有序，对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。

 

稳定性：

排序算法的稳定性:若待排序的序列中，存在多个具有相同关键字的记录，经过排序， 这些记录的相对次序保持不变，则称该算法是稳定的；若经排序后，记录的相对 次序发生了改变，则称该算法是不稳定的。 

     稳定性的好处：排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，可以避免多余的比较；

稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序

不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序

 

选择排序算法准则：

每种排序算法都各有优缺点。因此，在实用时需根据不同情况适当选用，甚至可以将多种方法结合起来使用。

选择排序算法的依据

影响排序的因素有很多，平均时间复杂度低的算法并不一定就是最优的。相反，有时平均时间复杂度高的算法可能更适合某些特殊情况。同时，选择算法时还得考虑它的可读性，以利于软件的维护。一般而言，需要考虑的因素有以下四点：

1．待排序的记录数目n的大小；

2．记录本身数据量的大小，也就是记录中除关键字外的其他信息量的大小；

3．关键字的结构及其分布情况；

4．对排序稳定性的要求。

设待排序元素的个数为n.

1）当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。

   快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；

       堆排序 ：  如果内存空间允许且要求稳定性的，

       归并排序：它有一定数量的数据移动，所以我们可能过与插入排序组合，先获得一定长度的序列，然后再合并，在效率上将有所提高。

2）  当n较大，内存空间允许，且要求稳定性 =》归并排序

3）当n较小，可采用直接插入或直接选择排序。

    直接插入排序：当元素分布有序，直接插入排序将大大减少比较次数和移动记录的次数。

    直接选择排序 ：元素分布有序，如果不要求稳定性，选择直接选择排序

5）一般不使用或不直接使用传统的冒泡排序。

6）基数排序

它是一种稳定的排序算法，但有一定的局限性：

　　1、关键字可分解。

　　2、记录的关键字位数较少，如果密集更好

　　3、如果是数字时，最好是无符号的，否则将增加相应的映射复杂度，可先将其正负分开排序。

 

注明：转载请提示出处：http://blog.csdn.net/hguisu/article/details/7776068

 

 

 

感谢您的支持，我会继续努力的! 扫码打赏，你说多少就多少

         

现在的IT行业并不像以前那么好混了，从业人员过多，导致初级程序员过剩，这也间接导致了公司的招聘门槛越来越高，要求程序员掌握的知识也越来越多。

算法也是一个争论了很久的话题，程序员到底该不该掌握算法？不同的人有不同的答案，而事实上，很多公司都对算法有一定的要求，有些公司直接在面试的时候便会要求面试者手写算法题。这就对程序员的技术要求产生了很大的考验，所以面对如今的大环境，我们必须掌握算法，才能在今后的工作中占据一席之地。

那么接下来，我就简单介绍一下几个排序算法，希望对你们有所帮助。
1.冒泡排序
冒泡排序（Bubble Sort），是一种较简单的排序算法。

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

演示：



代码如下：
@Test
public void bubbleSort() {
	int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
	// 统计比较次数
	int count = 0;
	// 第一轮比较
	for (int i = 0; i < arr.length - 1; i++) {
		// 第二轮比较
		for (int j = 0; j < arr.length - 1 - i; j++) {
			if (arr[j] > arr[j + 1]) {
				// 交换位置
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
			count++;
		}
	}
	System.out.println(Arrays.toString(arr));
	System.out.println("一共比较了:" + count + "次");
}

运行结果：
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
一共比较了:105次

这段代码相信大家都能够写出来，一般冒泡排序也就是这样写。但是这段程序有个缺点，就是当排序过程中已经将数组元素排序完成，但此时它仍然会去比较，这就做了无用功了，所以我们可以通过一个boolean变量来优化这段代，上面的程序中我们已经得出了比较次数为105次。

优化代码：
@Test
public void bubbleSort() {
	int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
	// 统计比较次数
	int count = 0;
	for (int i = 0; i < arr.length - 1; i++) {
		boolean flag = true;
		for (int j = 0; j < arr.length - 1 - i; j++) {
			if (arr[j] > arr[j + 1]) {
				// 交换位置
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
				flag = false;
			}
			count++;
		}
		if(flag) {
			break;
		}
	}
	System.out.println(Arrays.toString(arr));
	System.out.println("一共比较了:" + count + "次");
}

运行结果：
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
一共比较了:95次

我们首先在开始循环时定义了一个boolean变量为true，然后如果元素之间进行了交换，就将值置为false。所以，我们就可以通过这个boolean变量来判断是否有元素进行了交换。如果boolean变量为true，则证明没有元素进行交换，那么久说明此时的数组元素已经完成排序，那么跳出外层循环即可，否则就继续排序。通过结果也可以看出，比较次数确实是减少了很多。
2.选择排序
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

演示：



代码如下：
@Test
public void SelectionSort() {
	int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
	for (int i = 0; i < arr.length - 1; i++) {
		int index = i;
		for (int j = 1 + i; j < arr.length; j++) {
			if (arr[j] < arr[index]) {
				index = j;// 保存最小元素的下标
			}
		}
		// 此时已经找到最小元素的下标
		// 将最小元素与前面的元素交换
		int temp = arr[index];
		arr[index] = arr[i];
		arr[i] = temp;
	}
	System.out.println(Arrays.toString(arr));
}

运行结果：
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

实现也非常的简单，首先在外循环里定义了一个index变量存储i的值，这是为了避免重复地比较，因为在每一轮的比较结束后，前i个元素是已经排好序的，所以无需再次比较，只需从i开始即可。后面的比较都是基于index位置的元素进行比较，倘若比较完后index位置的元素是最小值，那就无需交换，不动即可。而如果找到了比index位置的元素更小的元素，那就将该元素的索引赋值给index，然后继续比较，直到比较完成，比较完成之后得到的index即为数组中的最小值，那此时只需要将index位置的元素和i位置的元素交换即可。
3.插入排序
插入排序（Insertion sort）是一种简单直观且稳定的排序算法。如果有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。

插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入到前面已经排序的数组中的适当位置上，直到全部插入完为止。

演示：



代码如下：
@Test
public void InsertionSort() {
	int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
	for (int i = 1; i < arr.length; i++) {
		// 定义待插入的数
		int insertValue = arr[i];
		// 找到待插入数的前一个数的下标
		int insertIndex = i - 1;
		while (insertIndex >= 0 && insertValue < arr[insertIndex]) {
			arr[insertIndex + 1] = arr[insertIndex];
			insertIndex--;
		}
		arr[insertIndex + 1] = insertValue;
	}
	System.out.println(Arrays.toString(arr));
}

运行结果：
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

那么在这里，因为数组元素我们并不确定，所以只能将数组的第一个元素看成是一个有序的序列，所以从数组的第二个元素开始才是我们需要去寻找插入位置的元素。所以外层循环从1开始，然后将arr[i]，也就是当前的第二个元素先保存起来，然后找到待插入元素的前一个元素下标，也就是i-1，此时通过一个while循环去比较。

当insertIndex小于0时应该退出循环，因为此时已经与前面的所有元素比较完毕。在比较的过程中，如果待插入元素小于前一个元素，就将前一个元素后移，也就是将前一个元素的值直接赋值给待插入元素位置。因为在最开始已经将待插入元素进行了保存，所以只需将待插入元素的值赋值给它的前一个元素即可。因为在while循环中insertIndex执行了自减操作，所以它的前一个元素下标应为insertIndex + 1。而如果待插入的元素值大于前一个元素，那么就不会进入while循环，这样insertIndex + 1之后的位置仍然是自己所在的位置，所以赋值后值不改变，后面的操作以此类推。
4.希尔排序
传统的插入排序算法在某些场景中存在着一些问题，例如[2，3，4，5，1]这样的一个数组，当我们对其进行插入排序的时候，发现要插入的数字是1，而要想将1插入到最前面，需要经过四个步骤，分别将5、4、3、2后移。所以得出结论：如果较小的数是我们需要进行插入的数，那效率就会比较低。鉴于这种场景的缺陷，希尔排序诞生了，它是插入排序的一种更高效的版本。

先看看希尔排序的概念：

希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
演示：



动画如果没有看懂，我这里再贴几张静态图：



代码实现：
@Test
public void ShellSort() {
	int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
	for (int gap = arr.length / 2; gap > 0; gap /= 2) {
		// 对数组元素进行分组
		for (int i = gap; i < arr.length; i++) {
			// 遍历各组中的元素
			for (int j = i - gap; j >= 0; j -= gap) {
				// 交换元素
				if (arr[j] > arr[j + gap]) {
					int temp = arr[j];
					arr[j] = arr[j + gap];
					arr[j + gap] = temp;
				}
			}
		}
	}

	System.out.println(Arrays.toString(arr));
}

运行结果：
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

那么在上面的程序段中，数组长度为15，所以在第一轮，数组被分为了15 / 2 = 7个小组，然后分别对每个小组的元素进行遍历。在第一轮中小组之间的元素间隔都为7，所以分成的小组数其实也就是元素之间的间隔。接着就可以对每个小组的元素进行比较，然后进行交换，接下来以此类推。
推荐阅读
程序员那些必须掌握的排序算法(下)

 

排序算法是《数据结构与算法》中最基本的算法之一。

排序算法可以分为内部排序和外部排序。

内部排序是数据记录在内存中进行排序。

而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。

常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。

用一张图概括：



时间复杂度与空间复杂度

关于时间复杂度：


	
平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。
	
	

	
线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序；
	
	

	
O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。 希尔排序
	
	

	
线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。
	
关于稳定性：


	
稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。
	
	

	
不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。
	
1. 冒泡排序

1.1 算法步骤


	
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
	
	

	
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
	
	

	
针对所有的元素重复以上的步骤，除了最后一个。
	
	

	
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
	
1.2 动画演示



 

冒泡排序动画演示

1.3 参考代码

 1// Java 代码实现
 2public class BubbleSort implements IArraySort {
 3
 4    @Override
 5    public int[] sort(int[] sourceArray) throws Exception {
 6        // 对 arr 进行拷贝，不改变参数内容
 7        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
 8
 9        for (int i = 1; i < arr.length; i++) {
10            // 设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。
11            boolean flag = true;
12
13            for (int j = 0; j < arr.length - i; j++) {
14                if (arr[j] > arr[j + 1]) {
15                    int tmp = arr[j];
16                    arr[j] = arr[j + 1];
17                    arr[j + 1] = tmp;
18
19                    flag = false;
20                }
21            }
22
23            if (flag) {
24                break;
25            }
26        }
27        return arr;
28    }
29}


2. 选择排序

2.1 算法步骤


	
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
	
	

	
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
	
	

	
重复第二步，直到所有元素均排序完毕。
	
2.2 动画演示



 

选择排序动画演示

2.3 参考代码

 1//Java 代码实现
 2public class SelectionSort implements IArraySort {
 3
 4    @Override
 5    public int[] sort(int[] sourceArray) throws Exception {
 6        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
 7
 8        // 总共要经过 N-1 轮比较
 9        for (int i = 0; i < arr.length - 1; i++) {
10            int min = i;
11
12            // 每轮需要比较的次数 N-i
13            for (int j = i + 1; j < arr.length; j++) {
14                if (arr[j] < arr[min]) {
15                    // 记录目前能找到的最小值元素的下标
16                    min = j;
17                }
18            }
19
20            // 将找到的最小值和i位置所在的值进行交换
21            if (i != min) {
22                int tmp = arr[i];
23                arr[i] = arr[min];
24                arr[min] = tmp;
25            }
26
27        }
28        return arr;
29    }
30}


3. 插入排序

3.1 算法步骤


	
将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
	
	

	
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
	
3.2 动画演示



 

插入排序动画演示

3.3 参考代码

 1//Java 代码实现
 2public class InsertSort implements IArraySort {
 3
 4    @Override
 5    public int[] sort(int[] sourceArray) throws Exception {
 6        // 对 arr 进行拷贝，不改变参数内容
 7        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
 8
 9        // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
10        for (int i = 1; i < arr.length; i++) {
11
12            // 记录要插入的数据
13            int tmp = arr[i];
14
15            // 从已经排序的序列最右边的开始比较，找到比其小的数
16            int j = i;
17            while (j > 0 && tmp < arr[j - 1]) {
18                arr[j] = arr[j - 1];
19                j--;
20            }
21
22            // 存在比其小的数，插入
23            if (j != i) {
24                arr[j] = tmp;
25            }
26
27        }
28        return arr;
29    }
30}


4. 希尔排序

4.1 算法步骤


	
选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
	
	

	
按增量序列个数 k，对序列进行 k 趟排序；
	
	

	
每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
	
4.2 动画演示



 

希尔排序动画演示

4.3 参考代码

 1//Java 代码实现
 2public class ShellSort implements IArraySort {
 3
 4    @Override
 5    public int[] sort(int[] sourceArray) throws Exception {
 6        // 对 arr 进行拷贝，不改变参数内容
 7        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
 8
 9        int gap = 1;
10        while (gap < arr.length) {
11            gap = gap * 3 + 1;
12        }
13
14        while (gap > 0) {
15            for (int i = gap; i < arr.length; i++) {
16                int tmp = arr[i];
17                int j = i - gap;
18                while (j >= 0 && arr[j] > tmp) {
19                    arr[j + gap] = arr[j];
20                    j -= gap;
21                }
22                arr[j + gap] = tmp;
23            }
24            gap = (int) Math.floor(gap / 3);
25        }
26
27        return arr;
28    }
29}


5. 归并排序

5.1 算法步骤


	
申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
	
	

	
设定两个指针，最初位置分别为两个已经排序序列的起始位置；
	
	

	
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
	
	

	
重复步骤 3 直到某一指针达到序列尾；
	
	

	
将另一序列剩下的所有元素直接复制到合并序列尾。
	
5.2 动画演示



 

归并排序动画演示

5.3 参考代码

 1//Java 代码实现
     public class MergeSort implements IArraySort {
 2
 3    @Override
 4    public int[] sort(int[] sourceArray) throws Exception {
 5        // 对 arr 进行拷贝，不改变参数内容
 6        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
 7
 8        if (arr.length < 2) {
 9            return arr;
10        }
11        int middle = (int) Math.floor(arr.length / 2);
12
13        int[] left = Arrays.copyOfRange(arr, 0, middle);
14        int[] right = Arrays.copyOfRange(arr, middle, arr.length);
15
16        return merge(sort(left), sort(right));
17    }
18
19    protected int[] merge(int[] left, int[] right) {
20        int[] result = new int[left.length + right.length];
21        int i = 0;
22        while (left.length > 0 && right.length > 0) {
23            if (left[0] <= right[0]) {
24                result[i++] = left[0];
25                left = Arrays.copyOfRange(left, 1, left.length);
26            } else {
27                result[i++] = right[0];
28                right = Arrays.copyOfRange(right, 1, right.length);
29            }
30        }
31
32        while (left.length > 0) {
33            result[i++] = left[0];
34            left = Arrays.copyOfRange(left, 1, left.length);
35        }
36
37        while (right.length > 0) {
38            result[i++] = right[0];
39            right = Arrays.copyOfRange(right, 1, right.length);
40        }
41
42        return result;
43    }
44
45}


6. 快速排序

6.1 算法步骤


	
从数列中挑出一个元素，称为 “基准”（pivot）;
	
	

	
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
	
	

	
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
	
6.2 动画演示



 

快速排序动画演示

6.3 参考代码

 1//Java 代码实现
 2public class QuickSort implements IArraySort {
 3
 4    @Override
 5    public int[] sort(int[] sourceArray) throws Exception {
 6        // 对 arr 进行拷贝，不改变参数内容
 7        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
 8
 9        return quickSort(arr, 0, arr.length - 1);
10    }
11
12    private int[] quickSort(int[] arr, int left, int right) {
13        if (left < right) {
14            int partitionIndex = partition(arr, left, right);
15            quickSort(arr, left, partitionIndex - 1);
16            quickSort(arr, partitionIndex + 1, right);
17        }
18        return arr;
19    }
20
21    private int partition(int[] arr, int left, int right) {
22        // 设定基准值（pivot）
23        int pivot = left;
24        int index = pivot + 1;
25        for (int i = index; i <= right; i++) {
26            if (arr[i] < arr[pivot]) {
27                swap(arr, i, index);
28                index++;
29            }
30        }
31        swap(arr, pivot, index - 1);
32        return index - 1;
33    }
34
35    private void swap(int[] arr, int i, int j) {
36        int temp = arr[i];
37        arr[i] = arr[j];
38        arr[j] = temp;
39    }
40
41}


7. 堆排序

7.1 算法步骤


	
创建一个堆 H[0……n-1]；
	
	

	
把堆首（最大值）和堆尾互换；
	
	

	
把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
	
	

	
重复步骤 2，直到堆的尺寸为 1。
	
7.2 动画演示



                                                                     堆排序动画演示

7.3 参考代码

 1//Java 代码实现
 2public class HeapSort implements IArraySort {
 3
 4    @Override
 5    public int[] sort(int[] sourceArray) throws Exception {
 6        // 对 arr 进行拷贝，不改变参数内容
 7        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
 8
 9        int len = arr.length;
10
11        buildMaxHeap(arr, len);
12
13        for (int i = len - 1; i > 0; i--) {
14            swap(arr, 0, i);
15            len--;
16            heapify(arr, 0, len);
17        }
18        return arr;
19    }
20
21    private void buildMaxHeap(int[] arr, int len) {
22        for (int i = (int) Math.floor(len / 2); i >= 0; i--) {
23            heapify(arr, i, len);
24        }
25    }
26
27    private void heapify(int[] arr, int i, int len) {
28        int left = 2 * i + 1;
29        int right = 2 * i + 2;
30        int largest = i;
31
32        if (left < len && arr[left] > arr[largest]) {
33            largest = left;
34        }
35
36        if (right < len && arr[right] > arr[largest]) {
37            largest = right;
38        }
39
40        if (largest != i) {
41            swap(arr, i, largest);
42            heapify(arr, largest, len);
43        }
44    }
45
46    private void swap(int[] arr, int i, int j) {
47        int temp = arr[i];
48        arr[i] = arr[j];
49        arr[j] = temp;
50    }
51
52}


8. 计数排序

8.1 算法步骤


	
花O(n)的时间扫描一下整个序列 A，获取最小值 min 和最大值 max
	
	

	
开辟一块新的空间创建新的数组 B，长度为 ( max - min + 1)
	
	

	
数组 B 中 index 的元素记录的值是 A 中某元素出现的次数
	
	

	
最后输出目标整数序列，具体的逻辑是遍历数组 B，输出相应元素以及对应的个数
	
8.2 动画演示



 

计数排序动画演示

8.3 参考代码

 1//Java 代码实现
 2public class CountingSort implements IArraySort {
 3
 4    @Override
 5    public int[] sort(int[] sourceArray) throws Exception {
 6        // 对 arr 进行拷贝，不改变参数内容
 7        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
 8
 9        int maxValue = getMaxValue(arr);
10
11        return countingSort(arr, maxValue);
12    }
13
14    private int[] countingSort(int[] arr, int maxValue) {
15        int bucketLen = maxValue + 1;
16        int[] bucket = new int[bucketLen];
17
18        for (int value : arr) {
19            bucket[value]++;
20        }
21
22        int sortedIndex = 0;
23        for (int j = 0; j < bucketLen; j++) {
24            while (bucket[j] > 0) {
25                arr[sortedIndex++] = j;
26                bucket[j]--;
27            }
28        }
29        return arr;
30    }
31
32    private int getMaxValue(int[] arr) {
33        int maxValue = arr[0];
34        for (int value : arr) {
35            if (maxValue < value) {
36                maxValue = value;
37            }
38        }
39        return maxValue;
40    }
41
42}


9. 桶排序

9.1 算法步骤


	
设置固定数量的空桶。
	
	

	
把数据放到对应的桶中。
	
	

	
对每个不为空的桶中数据进行排序。
	
	

	
拼接不为空的桶中数据，得到结果
	
9.2 动画演示



 

                                                                         桶排序动画演示

9.3 参考代码

 1//Java 代码实现
 2public class BucketSort implements IArraySort {
 3
 4    private static final InsertSort insertSort = new InsertSort();
 5
 6    @Override
 7    public int[] sort(int[] sourceArray) throws Exception {
 8        // 对 arr 进行拷贝，不改变参数内容
 9        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
10
11        return bucketSort(arr, 5);
12    }
13
14    private int[] bucketSort(int[] arr, int bucketSize) throws Exception {
15        if (arr.length == 0) {
16            return arr;
17        }
18
19        int minValue = arr[0];
20        int maxValue = arr[0];
21        for (int value : arr) {
22            if (value < minValue) {
23                minValue = value;
24            } else if (value > maxValue) {
25                maxValue = value;
26            }
27        }
28
29        int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
30        int[][] buckets = new int[bucketCount][0];
31
32        // 利用映射函数将数据分配到各个桶中
33        for (int i = 0; i < arr.length; i++) {
34            int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
35            buckets[index] = arrAppend(buckets[index], arr[i]);
36        }
37
38        int arrIndex = 0;
39        for (int[] bucket : buckets) {
40            if (bucket.length <= 0) {
41                continue;
42            }
43            // 对每个桶进行排序，这里使用了插入排序
44            bucket = insertSort.sort(bucket);
45            for (int value : bucket) {
46                arr[arrIndex++] = value;
47            }
48        }
49
50        return arr;
51    }
52
53    /**
54     * 自动扩容，并保存数据
55     *
56     * @param arr
57     * @param value
58     */
59    private int[] arrAppend(int[] arr, int value) {
60        arr = Arrays.copyOf(arr, arr.length + 1);
61        arr[arr.length - 1] = value;
62        return arr;
63    }
64
65}


10. 基数排序

10.1 算法步骤


	
将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零
	
	

	
从最低位开始，依次进行一次排序
	
	

	
从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列
	
10.2 动画演示



 

                                                                        基数排序动画演示

10.3 参考代码

 1//Java 代码实现
 2public class RadixSort implements IArraySort {
 3
 4    @Override
 5    public int[] sort(int[] sourceArray) throws Exception {
 6        // 对 arr 进行拷贝，不改变参数内容
 7        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
 8
 9        int maxDigit = getMaxDigit(arr);
10        return radixSort(arr, maxDigit);
11    }
12
13    /**
14     * 获取最高位数
15     */
16    private int getMaxDigit(int[] arr) {
17        int maxValue = getMaxValue(arr);
18        return getNumLenght(maxValue);
19    }
20
21    private int getMaxValue(int[] arr) {
22        int maxValue = arr[0];
23        for (int value : arr) {
24            if (maxValue < value) {
25                maxValue = value;
26            }
27        }
28        return maxValue;
29    }
30
31    protected int getNumLenght(long num) {
32        if (num == 0) {
33            return 1;
34        }
35        int lenght = 0;
36        for (long temp = num; temp != 0; temp /= 10) {
37            lenght++;
38        }
39        return lenght;
40    }
41
42    private int[] radixSort(int[] arr, int maxDigit) {
43        int mod = 10;
44        int dev = 1;
45
46        for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
47            // 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
48            int[][] counter = new int[mod * 2][0];
49
50            for (int j = 0; j < arr.length; j++) {
51                int bucket = ((arr[j] % mod) / dev) + mod;
52                counter[bucket] = arrayAppend(counter[bucket], arr[j]);
53            }
54
55            int pos = 0;
56            for (int[] bucket : counter) {
57                for (int value : bucket) {
58                    arr[pos++] = value;
59                }
60            }
61        }
62
63        return arr;
64    }
65    private int[] arrayAppend(int[] arr, int value) {
66        arr = Arrays.copyOf(arr, arr.length + 1);
67        arr[arr.length - 1] = value;
68        return arr;
69    }
70}


 

❤️ 看完三件事：

如果你觉得这篇内容对你挺有启发，我想邀请你帮我三个忙：


	
点赞，让更多的人也能看到这篇内容（收藏不点赞，都是耍流氓 -_-）
	
	

	
关注我和专栏，让我们成为长期关系
	
	

	
关注公众号「五分钟学算法」，第一时间阅读最新的算法文章，公众号后台回复 1024 送你 50 本 算法编程书籍。