常用排序算法
<h1>排序算法</h1>
<h2>1 术语说明</h2>
<ul>
<li>稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；</li>
<li>不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；</li>
<li>内排序：所有排序操作都在内存中完成；</li>
<li>外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；</li>
<li>时间复杂度： 一个算法执行所耗费的时间。</li>
<li>空间复杂度：运行完一个程序所需内存的大小。</li>
<li>n: 数据规模</li>
<li>k: “桶”的个数</li>
<li>In-place: 占用常数内存，不占用额外内存</li>
<li>Out-place: 占用额外内存</li>
</ul>
<h2>2 算法分类</h2>
<p><img src="https://s2.ax1x.com/2019/12/17/Qo1rcR.png" alt="排序算法分类" /></p>
<ol>
<li>排序可以分为内部排序和外部排序；</li>
<li>内部排序可以分为插入、选择、交换、归并、基数排序等；</li>
<li>插入排序可以分为直接插入排序、希尔排序、折半插入排序等；</li>
<li>选择排序可以分为简单选择排序、堆排序等；</li>
<li>交换排序可以分为冒泡排序、快速排序等；</li>
</ol>
<h3>2.1 比较排序和非比较排序</h3>
<h4>2.1.1 比较排序</h4>
<p>常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序。在排序的最终结果里，元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较，才能确定自己的位置。
在冒泡排序之类的排序中，问题规模为n，又因为需要比较n次，所以平均时间复杂度为O(n²)。在归并排序、快速排序之类的排序中，问题规模通过分治法消减为logN次，所以时间复杂度平均O(nlogn)。
比较排序的优势是，适用于各种规模的数据，也不在乎数据的分布，都能进行排序。可以说，比较排序适用于一切需要排序的情况。</p>
<h4>2.1.2 非比较排序</h4>
<p>基数排序、桶排序则属于非比较排序。非比较排序是通过确定每个元素之前，应该有多少个元素来排序。针对数组arr，计算arr[i]之前有多少个元素，则唯一确定了arr[i]在排序后数组中的位置。
非比较排序只要确定每个元素之前的已有的元素个数即可，所有一次遍历即可解决。算法时间复杂度O(n)。
非比较排序时间复杂度底，但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。</p>
<h2>3 简单插入排序</h2>
<p>设计初衷是往有序的数组中快速插入一个新的元素。</p>
<h3>3.1 基本思想</h3>
<p>基本思想是：将数组中的所有元素依次跟前面已经排好的元素相比较，如果选择的元素比已排序的元素小，则交换，直到全部元素都比较过为止。</p>
<h3>3.2 代码实现</h3>
<pre><code>/**
* 直接插入排序
*基本思想：将数组中的所有元素依次跟前面已经排好的元素相比较，
* 如果选择的元素比已排序的元素小，则交换，直到全部元素都比较过为止。
*
* 1. 从第一个元素开始，该元素可以认为已经被排序
* 2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
* 3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
* 4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
* 5. 将新元素插入到该位置后
* 6. 重复步骤2~5
* @param array
* @return
*/
public int[] insertSort(int[] array){
int temp;
for (int i=0;i<array.length-1;i++){
for (int j=i+1;j>0;j--){
if (array[j]<array[j-1]){
temp = array[j];
array[j] = array[j-1];
array[j-1] = temp;
}
}
}
return array;
}</code></pre>
<p><img src="https://s2.ax1x.com/2019/12/17/Qo8nJg.gif" alt="插入排序" /></p>
<h3>3.3 小结</h3>
<p>由于直接插入排序每次只移动一个元素的位， 并不会改变值相同的元素之间的排序， 因此它是一种稳定排序。</p>
<h2>4 希尔排序</h2>
<p>希尔排序，也称递减增量排序算法，是插入排序的一种高速而稳定的改进版本，它会优先比较距离较远的元素。</p>
<p>希尔排序是先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。</p>
<h3>4.1 基本思想</h3>
<p>将待排序数组按照步长gap进行分组，然后将每组的元素利用直接插入排序的方法进行排序；每次再将gap折半减小，循环上述操作；当gap=1时，利用直接插入，完成排序。
步长的选择是希尔排序的重要部分，一般选择为gap=length/2。</p>
<h3>4.2 代码实现</h3>
<pre><code>/**
* 希尔排序
*
* 1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；（一般初次取数组半长，之后每次再减半，直到增量为1）
* 2. 按增量序列个数k，对序列进行k 趟排序；
* 3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。
* 仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
* @param arr 待排序数组
* @return
*/
public int[] shellSort(int[] arr) {
int gap = arr.length / 2;
int temp;
while (gap > 0) { //不断缩小gap，直到1为止
for (int j = 0; (j+gap) < arr.length; j++){//使用gap进行分组
for(int k = 0; (k+gap)< arr.length; k += gap){//使用当前gap进行组内插入排序
if(arr[k] > arr[k+gap]) {
temp = arr[k+gap]; //交换操作
arr[k+gap] = arr[k];
arr[k] = temp;
}
}
}
gap /= 2;
}
return arr;
}</code></pre>
<p><img src="https://s2.ax1x.com/2019/12/17/Qo81Lq.gif" alt="希尔排序" /></p>
<h2>5 简单选择排序</h2>
<h3>5.1 基本思想</h3>
<p>首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。</p>
<h3>5.2 代码实现</h3>
<pre><code>/**
* 选择排序
*
* 1. 从待排序序列中，找到值最小的元素；
* 2. 如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；
* 3. 从余下的 N - 1 个元素中，找出关键字最小的元素，重复①、②步，直到排序结束。
* 仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
* @param array
* @return
*/
public int[] selectionSort(int[] array){
int temp,min;
for (int i=0;i<array.length-1;i++){
min = i;
for (int j=i+1;j<array.length;j++){
if(array[j]<array[min]){
min = j;
}
}
temp =array[i];
array[i] = array[min];
array[min] = temp;
}
return array;
}</code></pre>
<p><img src="https://s2.ax1x.com/2019/12/17/Qo88e0.gif" alt="选择排序" /></p>
<h3>5.3 小结</h3>
<p>无论是哪种情况，哪怕原数组已排序完成，它也将花费将近n²/2次遍历来确认一遍。即便是这样，它的排序结果也还是不稳定的。 唯一值得高兴的是，它并不耗费额外的内存空间。</p>
<h2>6 堆排序</h2>
<p>利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，利用数组来存储数据，不需要指针。</p>
<p>堆分为两种：最大堆和最小堆，两者的差别在于节点的排序方式。</p>
<p>在最大堆中，父节点的值比每一个子节点的值都要大。在最小堆中，父节点的值比每一个子节点的值都要小。这就是所谓的“堆属性”，并且这个属性对堆中的每一个节点都成立。</p>
<h3>6.1 基本思想</h3>
<p>以最大堆为例，堆排序的过程就是将待排序的序列构造成一个堆，选出堆中最大的移走，再把剩余的元素调整成堆，找出最大的再移走，重复直至有序。</p>
<h3>6.2 代码实现</h3>
<pre><code>/**
* 堆排序
*
* 1. 先将初始序列K[1..n]建成一个大顶堆, 那么此时第一个元素K1最大, 此堆为初始的无序区.
* 2. 再将关键字最大的记录K1 (即堆顶, 第一个元素)和无序区的最后一个记录 Kn 交换, 由此得到新的无序区K[1..n−1]和有序区K[n], 且满足K[1..n−1].keys⩽K[n].key
* 3. 交换K1 和 Kn 后, 堆顶可能违反堆性质, 因此需将K[1..n−1]调整为堆. 然后重复步骤②, 直到无序区只有一个元素时停止.
* @param arr 待排序数组
*/
public int[] heapSort(int []arr){
//1.构建大顶堆
//父节点i的左子节点：2i+1，右子节点：2i+2；子节点i的父节点：(i-1)/2
for(int i=(arr.length-1-1-1)/2;i>=0;i--){ //arr.length-1表示右下角的子节点
//从第一个非叶子结点从下至上，从右至左调整结构
adjustHeap(arr,i,arr.length);
}
System.out.println("MaxHeap:" + Arrays.toString(arr));
//2.调整堆结构+交换堆顶元素与末尾元素
for(int j=arr.length-1;j>0;j--){
swap(arr,0,j);//将堆顶元素与末尾元素进行交换
adjustHeap(arr,0,j);//重新对堆进行调整
System.out.println("MaxHeap:" + Arrays.toString(arr));
}
return arr;
}
/**
* 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
* @param arr
* @param i
* @param length
*/
public static void adjustHeap(int []arr,int i,int length){
int temp = arr[i];//先取出当前元素i
for(int k=i*2+1;k<length;k=k*2+1){//从i结点的左子结点开始，也就是2i+1处开始
if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点，k指向右子结点
k++;
}
if(arr[k] >temp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
arr[i] = arr[k];
i = k;
}else{
break;
}
}
arr[i] = temp;//将temp值放到最终的位置
}
</code></pre>
<p><img src="https://s2.ax1x.com/2019/12/17/Qo8tFU.gif" alt="堆排序" /></p>
<h3>6.3 小结</h3>
<ol>
<li>建立堆的过程, 从length/2 一直处理到0, 时间复杂度为O(n);</li>
<li>调整堆的过程是沿着堆的父子节点进行调整, 执行次数为堆的深度, 时间复杂度为O(lgn);</li>
<li>堆排序的过程由n次第②步完成, 时间复杂度为O(nlgn).</li>
</ol>
<p>由于堆排序中初始化堆的过程比较次数较多, 因此它不太适用于小序列. 同时由于多次任意下标相互交换位置, 相同元素之间原本相对的顺序被破坏了, 因此, 它是不稳定的排序.</p>
<h2>7 冒泡排序</h2>
<h3>7.1 基本思想</h3>
<p>重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。</p>
<h3>7.2 代码实现</h3>
<pre><code>/**
* 冒泡排序
*
* ①. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
* ②. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
* ③. 针对所有的元素重复以上的步骤，除了最后一个。
* ④. 持续每次对越来越少的元素重复上面的步骤①~③，直到没有任何一对数字需要比较。
* @param array 待排序数组
*/
public int[] bubbleSort(int[] array){
for (int i=array.length-1;i>0;i--){
for (int j=0;j<i;j++){
if (array[j]>array[j+1]){
swap(array,j,j+1);
}
}
}
return array;
}</code></pre>
<p><img src="https://s2.ax1x.com/2019/12/17/Qo1sj1.gif" alt="冒泡排序" /></p>
<h3>7.3 小结</h3>
<p>冒泡排序是最容易实现的排序, 最坏的情况是每次都需要交换, 共需遍历并交换将近n²/2次, 时间复杂度为O(n²). 最佳的情况是内循环遍历一次后发现排序是对的, 因此退出循环, 时间复杂度为O(n). 平均来讲, 时间复杂度为O(n²). 由于冒泡排序中只有缓存的temp变量需要内存空间, 因此空间复杂度为常量O(1).</p>
<p>由于冒泡排序只在相邻元素大小不符合要求时才调换他们的位置, 它并不改变相同元素之间的相对顺序, 因此它是稳定的排序算法.</p>
<h2>8 快速排序</h2>
<p>快速排序（Quicksort）是对冒泡排序的一种改进，借用了分治的思想</p>
<p>分治：分而治之，把一个复杂的问题分解成很多规模较小的子问题，然后解决这些子问题，把解决的子问题合并起来，大问题就解决了</p>
<h3>8.1 基本思想</h3>
<p>基本思想：挖坑填数+分治法。</p>
<p>首先选一个轴值(pivot，也有叫基准的)，通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。</p>
<h3>8.2 代码实现</h3>
<pre><code>/**
* 快速排序（递归）
*
* ①. 从数列中挑出一个元素，称为"基准"（pivot）。
* ②. 首先从后半部分开始，如果扫描到的值大于基准数据就让high减1,如果发现有元素比该基准数据的值小，就将high位置的值赋值给low位置
* ③. 然后开始从前往后扫描,如果扫描到的值小于基准数据就让low加1,如果发现有元素大于基准数据的值，就再将low位置的值赋值给high位置的值
* ④. 经过2、3步骤，"基准"就处于数列的中间位置；递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
* @param arr 待排序数组
* @param low 左边界
* @param high 右边界
*/
public int[] quickSort(int[] arr, int low, int high){
if(arr.length <= 0) return arr;
if(low >= high) return arr;
int left = low;
int right = high;
int temp = arr[left]; //挖坑1：保存基准的值
while (left < right){
while(left < right && arr[right] >= temp){ //坑2：从后向前找到比基准小的元素，插入到基准位置坑1中
right--;
}
arr[left] = arr[right];
while(left < right && arr[left] <= temp){ //坑3：从前往后找到比基准大的元素，放到刚才挖的坑2中
left++;
}
arr[right] = arr[left];
}
arr[left] = temp; //基准值填补到坑3中，准备分治递归快排
System.out.println("Sorting: " + Arrays.toString(arr));
quickSort(arr, low, left-1);
quickSort(arr, left+1, high);
return arr;
}</code></pre>
<p><img src="https://s2.ax1x.com/2019/12/17/Qo8QQs.gif" alt="快速排序" /></p>
<h3>8.3 小结</h3>
<p>快速排序排序效率非常高。 虽然它运行最糟糕时将达到O(n²)的时间复杂度, 但通常平均来看, 它的时间复杂为O(nlogn), 比同样为O(nlogn)时间复杂度的归并排序还要快. 快速排序似乎更偏爱乱序的数列, 越是乱序的数列, 它相比其他排序而言, 相对效率更高.</p>
<p>同选择排序相似, 快速排序每次交换的元素都有可能不是相邻的, 因此它有可能打破原来值为相同的元素之间的顺序. 因此, 快速排序并不稳定.</p>
<h2>9 归并排序</h2>
<p>归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。</p>
<p>归并排序其实要做两件事：</p>
<ul>
<li>分解：将序列每次折半拆分</li>
<li>合并：将划分后的序列段两两排序合并</li>
</ul>
<p>因此，归并排序实际上就是两个操作，拆分+合并</p>
<h3>9.1 基本思想</h3>
<p>归并排序算法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
归并排序可通过两种方式实现：</p>
<ul>
<li>自上而下的递归
<ol>
<li>将序列每相邻两个数字进行归并操作，形成 floor(n/2)个序列，排序后每个序列包含两个元素；</li>
<li>将上述序列再次归并，形成 floor(n/4)个序列，每个序列包含四个元素；</li>
<li>重复步骤2，直到所有元素排序完毕。</li>
</ol></li>
<li>自下而上的迭代
<ol>
<li>申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；</li>
<li>设定两个指针，最初位置分别为两个已经排序序列的起始位置；</li>
<li>比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；</li>
<li>重复步骤③直到某一指针到达序列尾；</li>
<li>将另一序列剩下的所有元素直接复制到合并序列尾。</li>
</ol></li>
</ul>
<h3>9.2 代码实现</h3>
<pre><code>/**
* 归并排序（递归）
*
* ①. 将序列每相邻两个数字进行归并操作，形成 floor(n/2)个序列，排序后每个序列包含两个元素；
* ②. 将上述序列再次归并，形成 floor(n/4)个序列，每个序列包含四个元素；
* ③. 重复步骤②，直到所有元素排序完毕。
* @param arr 待排序数组
*/
public int[] mergeSort(int[] arr){
if(arr.length <= 1) return arr;
int mid = arr.length >> 1;
int[] leftArr = Arrays.copyOfRange(arr, 0, mid);
int[] rightArr = Arrays.copyOfRange(arr, mid, arr.length);
System.out.println("split two array: " + Arrays.toString(leftArr) + " And " + Arrays.toString(rightArr));
return mergeTwoArray(mergeSort(leftArr), mergeSort(rightArr)); //不断拆分为最小单元，再排序合并
}
private int[] mergeTwoArray(int[] arr1, int[] arr2){
int i = 0, j = 0, k = 0;
int[] result = new int[arr1.length + arr2.length]; //申请额外的空间存储合并之后的数组
while(i < arr1.length && j < arr2.length){ //选取两个序列中的较小值放入新数组
if(arr1[i] <= arr2[j]){
result[k++] = arr1[i++];
}else{
result[k++] = arr2[j++];
}
}
//以下两个循环只有一个会执行,因为序列1和序列2中只有一个序列有多余元素
while(i < arr1.length){ //序列1中多余的元素移入新数组
result[k++] = arr1[i++];
}
while(j < arr2.length){ //序列2中多余的元素移入新数组
result[k++] = arr2[j++];
}
System.out.println("Merging: " + Arrays.toString(result));
return result;
}</code></pre>
<p><img src="https://s2.ax1x.com/2019/12/17/Qo8kLt.png" alt="归并排序" /></p>
<h3>9.3 小结</h3>
<p>从效率上看，归并排序可算是排序算法中的”佼佼者”. 假设数组长度为n，那么拆分数组共需logn，, 又每步都是一个普通的合并子数组的过程， 时间复杂度为O(n)， 故其综合时间复杂度为O(nlogn)。另一方面， 归并排序多次递归过程中拆分的子数组需要保存在内存空间， 其空间复杂度为O(n)。同时，归并排序是一种稳定的排序方法。
和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n log n）的时间复杂度。代价是需要额外的内存空间。</p>
<h2>10 基数排序</h2>
<p>基数排序（Radix sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。</p>
<h3>10.1 基本思想</h3>
<p>将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。</p>
<p>基数排序按照优先从高位或低位来排序有两种实现方案：</p>
<ul>
<li>
<p>MSD（Most significant digital） 从最左侧高位开始进行排序。
先按k1排序分组, 同一组中记录, 关键码k1相等, 再对各组按k2排序分成子组, 之后, 对后面的关键码继续这样的排序分组, 直到按最次位关键码kd对各子组排序后. 再将各组连接起来, 便得到一个有序序列。MSD方式适用于位数多的序列。</p>
</li>
<li>LSD （Least significant digital）从最右侧低位开始进行排序。
先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。LSD方式适用于位数少的序列。</li>
</ul>
<h3>10.2 代码实现</h3>
<pre><code>/**
* 基数排序（LSD 从低位开始）
*
* 基数排序适用于：
* (1)数据范围较小，建议在小于1000
* (2)每个数值都要大于等于0
*
* ①. 取得数组中的最大数，并取得位数；
* ②. arr为原始数组，从最低位开始取每个位组成radix数组；
* ③. 对radix进行计数排序（利用计数排序适用于小范围数的特点）；
* @param arr 待排序数组
*/
public int[] radixSort(int[] arr){
if(arr.length <= 1) return arr;
//取得数组中的最大数，并取得位数
int max = arr[0];
for(int i = 0; i < arr.length; i++){
if(max < arr[i]){
max = arr[i];
}
}
int maxDigit = 1;
while(max / 10 > 0){
maxDigit++;
max = max / 10;
}
System.out.println("maxDigit: " + maxDigit);
//申请一个桶空间，存放0-9，10个桶
int[][] buckets = new int[10][arr.length];
int base = 10;
//从低位到高位，对每一位遍历，将所有元素分配到桶中
for(int i = 0; i < maxDigit; i++){
int[] bktLen = new int[10]; //存储各个桶中存储元素的数量，10表示0-9，10个桶
//分配：将所有元素分配到桶中
for(int j = 0; j < arr.length; j++){
int whichBucket = (arr[j] % base) / (base / 10);//哪一个桶，一共10个
buckets[whichBucket][bktLen[whichBucket]] = arr[j];
bktLen[whichBucket]++;
}
//收集：将不同桶里数据挨个捞出来,为下一轮高位排序做准备,由于靠近桶底的元素排名靠前,因此从桶底先捞
int k = 0;
for(int b = 0; b < buckets.length; b++){//buckets.length 表示桶的个数，b表示哪一个桶
for(int p = 0; p < bktLen[b]; p++){//bktLen[b]表示b这个桶装的元素个数
arr[k++] = buckets[b][p];
}
}
System.out.println("Sorting: " + Arrays.toString(arr));
base *= 10;
}
return arr;
}</code></pre>
<p><img src="https://s2.ax1x.com/2019/12/17/QoUiQg.gif" alt="基数排序" /></p>
<h3>10.3 小结</h3>
<p>在基数排序中，因为没有比较操作，所以在复杂上，最好的情况与最坏的情况在时间上是一致的，均为 O(d*(n + r))。其中，d 为位数，r 为基数，n 为原数组个数。基数排序不改变相同元素之间的相对顺序，因此它是稳定的排序算法。</p>
<h2>11 计数排序</h2>
<h3>11.1 基本原理</h3>
<p>计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。</p>
<p>计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。</p>
<h3>11.2 代码实现</h3>
<pre><code>/**
* 计数排序
*
* 1、找出待排序的数组中最大和最小的元素；
* 2、统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
* 3、对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
* 4、反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
* @param array
* @return
*/
public static int[] countSort(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;
}</code></pre>
<p><img src="https://s2.ax1x.com/2019/12/17/Qo8Zo8.gif" alt="计数排序" /></p>
<h3>11.3 小结</h3>
<p>当输入的元素是n 个0到k之间的整数时，它的运行时间是 O(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。</p>
<h2>12 桶排序</h2>
<p>桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。</p>
<h3>12.1 基本原理</h3>
<p>桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排。
注意，如果递归使用桶排序为各个桶排序，则当桶数量为1时要手动减小BucketSize增加下一循环桶的数量，否则会陷入死循环，导致内存溢出。</p>
<h3>12.2 代码实现</h3>
<pre><code>/**
* 桶排序
*
* 1、人为设置一个BucketSize，作为每个桶所能放置多少个不同数值（例如当BucketSize==5时，该桶可以存放｛1,2,3,4,5｝这几种数字，但是容量不限，即可以存放100个3）；
* 2、遍历输入数据，并且把数据一个一个放到对应的桶里去；
* 3、对每个不是空的桶进行排序，可以使用其它排序方法，也可以递归使用桶排序；
* 4、从不是空的桶里把排好序的数据拼接起来。
* @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;
}</code></pre>
<p><img src="https://s2.ax1x.com/2019/12/17/Qo8lyn.png" alt="桶排序" /></p>
<h3>12.3 小结</h3>
<p>桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。</p>
<p>这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：</p>
<ul>
<li>基数排序：根据键值的每位数字来分配桶</li>
<li>计数排序：每个桶只存储单一键值</li>
<li>桶排序：每个桶存储一定范围的数值</li>
</ul>
<h2>算法总结</h2>
<table>
<thead>
<tr>
<th style="text-align: center;">排序算法</th>
<th style="text-align: center;">平均时间复杂度</th>
<th style="text-align: center;">最好情况</th>
<th style="text-align: center;">最坏情况</th>
<th style="text-align: center;">空间复杂度</th>
<th style="text-align: center;">排序方式</th>
<th style="text-align: center;">稳定性</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align: center;">直接插入排序</td>
<td style="text-align: center;">O(n^2)</td>
<td style="text-align: center;">O(n)</td>
<td style="text-align: center;">O(n^2)</td>
<td style="text-align: center;">O(1)</td>
<td style="text-align: center;">In-place</td>
<td style="text-align: center;">稳定</td>
</tr>
<tr>
<td style="text-align: center;">希尔排序</td>
<td style="text-align: center;">O(nlogn)</td>
<td style="text-align: center;">O(nlog^2n)</td>
<td style="text-align: center;">O(nlog^2n)</td>
<td style="text-align: center;">O(1)</td>
<td style="text-align: center;">In-place</td>
<td style="text-align: center;">不稳定</td>
</tr>
<tr>
<td style="text-align: center;">简单选择排序</td>
<td style="text-align: center;">O(n^2)</td>
<td style="text-align: center;">O(n^2)</td>
<td style="text-align: center;">O(n^2)</td>
<td style="text-align: center;">O(1)</td>
<td style="text-align: center;">In-place</td>
<td style="text-align: center;">不稳定</td>
</tr>
<tr>
<td style="text-align: center;">堆 排 序</td>
<td style="text-align: center;">O(nlogn)</td>
<td style="text-align: center;">O(logn)</td>
<td style="text-align: center;">O(nlogn)</td>
<td style="text-align: center;">O(1)</td>
<td style="text-align: center;">In-place</td>
<td style="text-align: center;">不稳定</td>
</tr>
<tr>
<td style="text-align: center;">冒泡排序</td>
<td style="text-align: center;">O(n^2)</td>
<td style="text-align: center;">O(n)</td>
<td style="text-align: center;">O(n^2)</td>
<td style="text-align: center;">O(1)</td>
<td style="text-align: center;">In-place</td>
<td style="text-align: center;">稳定</td>
</tr>
<tr>
<td style="text-align: center;">快速排序</td>
<td style="text-align: center;">O(nlogn)</td>
<td style="text-align: center;">O(logn)</td>
<td style="text-align: center;">O(n^2)</td>
<td style="text-align: center;">O(logn)</td>
<td style="text-align: center;">In-place</td>
<td style="text-align: center;">不稳定</td>
</tr>
<tr>
<td style="text-align: center;">归并排序</td>
<td style="text-align: center;">O(nlogn)</td>
<td style="text-align: center;">O(logn)</td>
<td style="text-align: center;">O(nlogn)</td>
<td style="text-align: center;">O(n)</td>
<td style="text-align: center;">Out-place</td>
<td style="text-align: center;">稳定</td>
</tr>
<tr>
<td style="text-align: center;">基数排序</td>
<td style="text-align: center;">O(n*k)</td>
<td style="text-align: center;">O(n*k)</td>
<td style="text-align: center;">O(n*k)</td>
<td style="text-align: center;">O(n+k)</td>
<td style="text-align: center;">Out-place</td>
<td style="text-align: center;">稳定</td>
</tr>
<tr>
<td style="text-align: center;">计数排序</td>
<td style="text-align: center;">O(n+k)</td>
<td style="text-align: center;">O(n+k)</td>
<td style="text-align: center;">O(n+k)</td>
<td style="text-align: center;">O(k)</td>
<td style="text-align: center;">Out-place</td>
<td style="text-align: center;">稳定</td>
</tr>
<tr>
<td style="text-align: center;">桶 排 序</td>
<td style="text-align: center;">O(n+k)</td>
<td style="text-align: center;">O(n+k)</td>
<td style="text-align: center;">O(n^2)</td>
<td style="text-align: center;">O(n+k)</td>
<td style="text-align: center;">Out-place</td>
<td style="text-align: center;">稳定</td>
</tr>
</tbody>
</table>
<h2>注</h2>
<p>可结合https://visualgo.net/zhjin</p>