0、0.11排序算法的说明 排序的定义
根据某个关键字对一序列对象进行排序。
0.2术语说明
稳定性:如果a原本在b前，而a=b,排序之后a仍然在b的前面；不稳定性:如果a原本在b前，而a=b,排序后，a可能出现在b后面；内部排序：所有排序操作都在内存中完成；外部排序：由于数据太大，数据放置在磁盘中，排序可以通过磁盘和内存的数据传输进行；时间复杂性：描述算法运行时间的函数，用大O符号表示；空间复杂性：描述算法所需的内存空间大小。0.3算法总结
图片名词解释：
n:数据规模
k:“桶”数
In-place:占用常数内存，不占用额外内存
Out-place:占用额外内存
0.5 算法分类
0.6 比较和非比较排序的区别
常见的快速排序、合并排序、堆叠排序、气泡排序等属于比较排序。在排序的最终结果中，元素之间的顺序取决于它们之间的比较。每个数字都必须与其他数字进行比较，以确定你的位置。
在冒泡排序等排序中，问题规模为n，平均时间复杂度为O，因为需要比较n次(n²)。在并购排序、快速排序等排序中，通过分治法将问题规模降低到logn次，因此平均时间复杂度为ogn次(nlogn)。
比较排序的优点是适用于各种规模的数据，不在乎数据的分布。可以说，比较排序适用于所有需要排序的情况。
计数排序、基数排序和桶排序属于非比较排序。非比较排序是通过确定每个元素之前应该有多少元素来排序的。计算数组arr[i]之前有多少元素是唯一确定arr的[i]排序后数组中的位置。
非比较排序可以通过确定每个元素之前的现有元素数量来解决。算法时间复杂性O(n)。
非比较排序的时间复杂性较低，但由于非比较排序需要占用空间来确定唯一的位置。因此，对数据规模和数据分布有一定的要求。
1、冒泡排序
泡沫排序是一种简单的排序算法。它反复访问要排序的数列，并一次比较两个元素。如果他们的顺序错了，交换它们。访问数列的工作是反复进行，直到不再需要交换，也就是说，数列已经排序完成。该算法的名称一直是因为通过交换，元素越小，它就会慢慢“浮动”到数列的顶部。
1.1 算法描述
相对相邻的元素。如果第一个比第二个大，交换两个；每对相邻元素做同样的工作，从第一对到最后一对，这样最后的元素应该是最大的；除最后一个外，所有元素重复上述步骤；重复步骤1~3，直到排序完成。1.2 动图演示
1.3代码实现
/** * 冒泡排序 * @param array * @return */ public static int[] bubbleSort(int[] array){ if(array.length > 0){ for(int i = 0;i<array.length;i++){ for(int j = 0;j<array.length - 1 - i;j++){ if(array[j] > array[j+1]){ int temp = array[j]; array[j] = array[j+1]; array[j+1] = temp; } } } } return array; }
1.4 算法分析
最佳情况：T(n) = O(n) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)
2、选择排序（Selection Sort）性能最稳定的排序算法之一是O（n2）的时间复杂性，因此数据规模越小越好。唯一的好处可能是它不会占用额外的内存空间。理论上，选择排名也可能是普通人通常想到的最常见的排名方法。
选择排序(Selection-sort)这是一个简单而直观的排序算法。其工作原理：首先在未排序的序列中找到最小（大）元素，存储在排序的起始位置，然后继续从剩余的未排序元素中找到最小（大）元素，然后放在已排序的序列的末尾。以此类推，直到所有元素都完成。
2.1 算法描述
n个记录的直接选择排序可通过n-1次直接选择排序获得有序结果。具体算法描述如下：
初始状态:无序区域为R[1..n]，有序区域为空；第一次排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。从目前的无序区域选择最小的关键字记录 R[k]，将其与无序区域的第一个记录R交换，使R[1..i]和R[i+1..n)分别变成记录数增加1个的新有序区和记录数减少1个的新无序区；n-一趟结束后，数组有序化。2.2 动图演示
2.3 代码实现
/** * 选择排序 * @param array * @return */ public static int[] selectionSort(int[] array){ if(array.length > 0){ 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; } } if(minIndex != i){ int temp = array[minIndex]; array[minIndex] = array[i]; array[i] = temp; } } } return array; }
2.4 算法分析
最佳情况：T(n) = O(n2) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)
3、插入排序（Insertion Sort）插入排序（Insertion-Sort）算法描述是一种简单直观的排序算法。其工作原理是构建有序列，在排序列中从后向前扫描未排序数据，找到相应的位置并插入。在实现插入排序时，通常采用in-place排序（即只使用O（1）的额外空间排序）。因此，在从后到前扫描的过程中，需要逐渐向后移动排序元素，为最新元素提供插入空间。
3.1 算法描述
一般来说，in-place在数组中实现插入排序。具体算法描述如下:
从第一个元素开始，可以认为元素已经排序；取出下一个元素，从后到前扫描排序元素序列；如果元素（排序）大于新元素，将元素移动到下一个位置；重复步骤3，直到找到排序元素小于或等于新元素的位置；将新元素插入位置；重复步骤2~5。3.2 动图演示
3.2 代码实现
/** * 插入排序 * @param array * @return */ public static int[] insertSort(int[] array){ if(array.length > 0){ for(int i = 0 ;i<array.length - 1;i++){ int current = array[i+1]; int index = i; while(index >= 0 && current < array[index]){ array[index + 1] = array[index]; index--; } array[index+1] = current; } } return array; }
3.4 算法分析
最佳情况：T(n) = O(n) 最坏情况：T(n) = O(n2) 平均情况：T(n) = O(n2)
4、希尔排序（Shell Sort）希尔的排名是希尔（Donald Shell）一种排序算法是在1959年提出的。希尔排名也是一种插入式排名，它是一个更有效的版本，也被称为减少增量排名，该算法是第一批突破O（n2）的算法之一。它与插入排序的区别在于，它将优先考虑距离较远的元素。又称减少增量排序，希尔排序。
希尔排序是将记录按下表中的一定增量分组，直接插入每组排序算法；随着增量的逐渐减少，每组包含越来越多的关键字。当增量减少到1时，整个文件被分成一组，算法终止。
4.1 算法描述
让我们来看看希尔排名的基本步骤。在这里，我们选择增量gap=length/2，继续以gap缩小增量 = gap我们可以用一个序列来表示这种增量选择，{n/2,(n/2)/2...1}，称为增量序列。希尔排名增量序列的选择和证明是一个数学问题。我们选择的增量序列更为常用，也是希尔推荐的增量，称为希尔增量，但事实上，这个增量序列并不是最好的。在这里，我们举例使用希尔增量。
将整个待排序的记录序列分成几个子序列，直接插入排序。具体算法描述:
t1，t2，选择增量序列，tk，其中ti>tj，tk=1；根据增量序列的数量k对序列进行k 每次排序，根据相应的增量ti，将待排序列分成几个长度为m 子序列分别直接插入和排序每个子表。仅增量因子为1 当整个序列作为表处理时，表长就是整个序列的长度。4.2 过程演示
4.3 代码实现
/** * 希尔排序 * @param array * @return */ public static int[] shellSort(int[] array){ if(array.length > 0){ int len = array.length; int gap = len / 2; while(gap > 0){ for(int i = gap;i < len;i++){ int temp = array[i]; int index = i - gap; while(index >= 0 && array[index] > temp){ array[index + gap] = array[index]; index -= gap; } array[index + gap] = temp; } gap /= 2; } } return array; }
4.4 算法分析
最佳情况：T(n) = O(nlog2 n) 最坏情况：T(n) = O(nlog2 n) 平均情况：T(n) =O(nlog2n)
5、归并排序（Merge Sort）与选择排序一样，合并排序的性能不受输入数据的影响，但性能比选择排序要好得多，因为它总是O(n log n）时间复杂。成本是需要额外的内存空间。
归并排序是基于归并操作的有效排序算法。该算法采用分治法（Divide and Conquer）一个非常典型的应用程序。合并排序是一种稳定的排序方法。合并有序的子序列，获得完全有序的序列；即使每个子序列都有序，然后使子序列段有序。如果将两个有序表合并成一个有序表，则称为2-道路合并。
5.1 算法描述
将长度为n的输入序列分为两个长度为n/2的子序列；两个子序列分别合并排序；将两个排序良好的子序列合并为最终排序序列。5.2 动图演示
5.3 代码实现
/** * 2路归并算法 * @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)); } 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; }
- 4 算法分析
最佳情况：T(n) = O(n) 最差情况：T(n) = O(nlogn) 平均情况：T(n) = O(nlogn)
6、快速排序（Quick Sort）快速排序的基本思想：将待排列记录分成两个独立的部分，其中一部分记录的关键字小于另一部分，这两部分记录可以继续排序，以实现整个顺序的有序。
6.1 算法描述
用分治法快速排序一串（list）分为两个子串（sub-lists）。具体算法描述如下：
从数列中挑出一个元素，称为 “基准”（pivot）；重新排序数列，所有元素比基准值小的放在基准前面，所有元素比基准值大的放在基准后面(相同的数量可以到达任何一边)。该分区退出后，该基准处于数列的中间。这叫分区（partition）操作；递归地（recursive）对小于基准值元素的子数列和大于基准值元素的子数列进行排序。6.2 动图演示
6.3 代码实现
/** * 快速排序算法 * @param array * @param low * @param hight */ public static void QuickSort(int[] array,int low,int hight){ //if (array.length < 1 || low < 0 || hight >= array.length || low > hight) return null; if(low < hight){ int privotpos = partition(array,low,hight); QuickSort(array,low,privotpos - 1); QuickSort(array,privotpos + 1,hight); } } public static int partition(int[] array,int low,int hight){ int privot = array[low]; while(low < hight){ while(low < hight && array[hight] >= privot) --hight; array[low] = array[hight]; while(low < hight && array[low] <= privot) ++low; array[hight] = array[low]; } array[low] = privot; return low; }
6.4 算法分析
最佳情况：T(n) = O(nlogn) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(nlogn)
7、堆排序（Heap Sort）堆的定义如下： {k1，n个元素的序列 k2, ... , kn}当满足条件时，称为堆。
堆可以看作是一棵完全的二叉树。此外，每个结点的值大于或等于儿童结点的值，称为大顶堆；或者每个结点的值小于或等于儿童结点的值，称为小顶堆。
堆排序(Heap Sort)这是一种利用堆进行排序的方法。其基本思想是将待排序列构建成大顶堆（或小顶堆）。整个序列的最大值（或最小值）是堆顶的根结点，交换根节点的值和堆数组的末端元素。此时，末端元素是最大值（或最小值），然后将剩余的n-1序列重构成堆，从而获得n个元素中的次大值（或次小值），从而反复执行，最终获得有序列。
7.1 算法描述
关键字序列(R1，R2....Rn)将堆顶元素R[1]和最后一个元素R构成一个大的顶堆，作为初始无序区域；[n]此时交换，得到新的无序区(R1，R2，...Rn-1)以及新的有序区(Rn),满足R[1，2..n-1]<=R[n]；由于交换后的新堆顶R[1]可能违反堆的性质，因此，对于目前的无序区(R1，R2...Rn-1)调整为新堆，然后将R[1]与无序区的最后一个元素交换，得到新的无序区(R1，R2...Rn-2)以及新的有序区(Rn-1,Rn)。在有序区域的元素数量为n-1之前，整个排序过程将不断重复这个过程。在有序区域的元素数量为n-1之前，整个排序过程将不断重复。7.2 动图演示
7.3 代码实现
/** * 调整堆 * @param array * @param index * @param length */ public static void heapAdjust(int[] array,int index,int length){ ///保存当前结点的下标 int max = index; ////当前节点左子节点下标 int lchild = 2*index; ////当前节点右子节点下标 int rchild = 2*index + 1; if(length > lchild && array[max] < array[lchild]){ max = lchild; } if(length > rchild && array[max] < array[rchild]){ max = rchild; } //如果这个节点比左右孩子的值小，将其与最大值交换，并调整堆 if(max != index){ int temp = array[index]; array[index] = array[max]; array[max] = temp; heapAdjust(array,max,length); } } /** * 堆排序 * @param array * @return */ public static int[] heapSort(int[] array){ int len = array.length; ///初始化堆，构建最大堆 for(int i = (len/2 - 1);i >= 0;i--){ heapAdjust(array,i,len); } //交换堆顶元素和最后一个元素，并重新调整堆 for(int i = len - 1;i > 0;i--){ int temp = array[i]; array[i] = array[0]; array[0] = temp; heapAdjust(array,0,i); } return array; }
7.4 算法分析
最佳情况：T(n) = O(nlogn) 最差情况：T(n) = O(nlogn) 平均情况：T(n) = O(nlogn)
8、计数排序（Counting Sort）计数排序的核心是将输入的数据值转换为键存储在额外开放的数组空间中。 计数排序要求输入的数据作为线性时间复杂度的排序，必须是具有一定范围的整数。
计数排序(Counting sort)这是一种稳定的排序算法。计数排序使用额外的数组C，其中第一个元素是等待数组A中值等于i的元素数。然后根据数组C将A中的元素排列到正确的位置。它只能对整数进行排序。
8.1 算法描述
找出要排序的数组中最大和最小的元素；统计数组中每个值为i元素出现的次数存储在数组C的第一项中；所有计数累加(从C中的第一个元素开始，每个元素加上前一个元素)；反向填充目标数组：将每个元素i放在新数组的C中(i)项，每个元素都会放C(i)减去1。8.2 动图演示
8.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 = 0;i < array.length;i++){ if(array[i] < min){ min = array[i]; } if(array[i] > max){ max = array[i]; } } //偏差 bias = 0 - min; ///新开一个数组 int[] bucket = new int[max - min +1]; ///数据初始化为0 Arrays.fill(bucket, 0); for(int i = 0;i < array.length;i++){ bucket[array[i] + bias] += 1; } int index = 0; for(int i = 0;i < bucket.length;i++){ int len = bucket[i]; while(len > 0){ array[index++] = i - bias; len --; } } return array; }
8.4 算法分析
当输入元素为n时 当0到k之间的整数时，它的运行时间是 O(n + k)。计数排序不是比较排序，排序速度比任何比较排序算法都快。由于用于计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值和最小值之间的差额加上1），因此需要大量的时间和内存来对数据范围较大的数组进行计数排序。
最佳情况：T(n) = O(n+k) 最差情况：T(n) = O(n+k) 平均情况：T(n) = O(n+k)
9、桶排序（Bucket Sort）桶排序是计数排序的升级版本。它利用了函数的映射关系，其效率的关键在于这个映射函数的确定。
桶排序 (Bucket sort)工作原理：假设输入数据服从均匀分布，将数据分配到有限数量的桶中，每个桶分别排序（可以使用其他排序算法或递归继续使用桶排序）
9.1 算法描述
人工设置一个bucketsize作为每个桶可以放置多少不同的值(例如，当bucketsize==5时，桶可以存放｛1,2,3,4,5｝这些数字，但容量不限，可以存放100个3)；将数据输入遍历，并将数据逐一放入相应的桶中；对每个不是空桶进行排序，可采用其它排序方法，也可以递归使用桶排序；从不在空桶中拼接排序数据。 请注意，如果递归用桶对每个桶进行排序，当桶数为1时，应手动减少bucketsize，以增加下一个循环桶的数量，否则会陷入死循环，导致内存溢出。
9.2 图片演示
9.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; }
9.4 算法分析
在最佳情况下，使用线性时间O(n)，桶排序的时间复杂性取决于每个桶之间数据排序的时间复杂性，因为其他部分的时间复杂性是O(n)。显然，桶的划分越小，每个桶之间的数据越少，排序所需的时间就越少。但相应的空间消耗会增加。
最佳情况：T(n) = O(n+k) 最差情况：T(n) = O(n+k) 平均情况：T(n) = O(n2)
10、基数排序（Radix Sort）基数排序也是一种非比较排序算法，对每个人进行排序，从最低水平排序，复杂性为O(kn),为数组长度，k为数组中最大的位数；
基数排序是按低排序，然后收集；然后按高排序，然后收集；类比，直到最高。有时有些属性有优先级，先按低优先级排序，然后按高优先级排序。最后的顺序是高优先级在前面，高优先级相同的低优先级在前面。基数排序是基于分别排序，分别收集，所以它是稳定的。
10.1 算法描述
获得数组中的最大数并获得位数；arr是原始数组，每个位数从最低位组成radix数组；对radix进行计数排序（使用适合小范围数的计数排序）；10.2 动图演示
10.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, p = 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 ,p *= 10){ for(int j = 0;j < array.length;j++){ int num = (array[j] % mod) / p; 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; }
10.4 算法分析
最佳情况：T(n) = O(n * k) 最差情况：T(n) = O(n * k) 平均情况：T(n) = O(n * k)
基数排序有两种方法：
MSD 从高位开始排序 LSD 排序从低位开始
基数排序 vs 计数排序 vs 桶排序
这三种排序算法都使用了桶的概念，但在桶的使用方法上存在明显差异：
基数排序：根据键值的每个数字分配桶计数排序：每个桶只存储单个键值桶排序：每个桶存储一定范围的值
以上所有代码都通过了实验，没有错。
湘公网安备43019002002060