所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。在各个领域中考虑到数据的各种限制和规范，要得到一个符合实际的优秀算法，得经过大量的推理和分析。
排序算法可以分为：
常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等，本文只讲解内部排序算法。用一张图概括：
十种常见排序算法可以分类两大类别：比较类排序和非比较类排序。
常见的快速排序、归并排序、堆排序以及冒泡排序等都属于比较类排序算法。比较类排序是通过比较来决定元素间的相对次序，由于其时间复杂度不能突破 O(nlogn)，因此也称为非线性时间比较类排序。在冒泡排序之类的排序中，问题规模为 n，又因为需要比较 n 次，所以平均时间复杂度为 O(n²)。在归并排序、快速排序之类的排序中，问题规模通过分治法消减为 logn 次，所以时间复杂度平均 O(nlogn)。
比较类排序的优势是，适用于各种规模的数据，也不在乎数据的分布，都能进行排序。可以说，比较排序适用于一切需要排序的情况。
而计数排序、基数排序、桶排序则属于非比较类排序算法。非比较排序不通过比较来决定元素间的相对次序，而是通过确定每个元素之前，应该有多少个元素来排序。由于它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。 非比较排序只要确定每个元素之前的已有的元素个数即可，所有一次遍历即可解决。算法时间复杂度 $O(n)$。
非比较排序时间复杂度底，但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。
冒泡排序是一种简单的排序算法。它重复地遍历要排序的序列，依次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历序列的工作是重复地进行直到没有再需要交换为止，此时说明该序列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢 “浮” 到数列的顶端。
/**
* 冒泡排序
* @param arr
* @return arr
*/
public static int[] bubbleSort(int[] arr) {
for (int i = 1; i arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
// Change flag
flag = false;
}
}
if (flag) {
break;
}
}
return arr;
}
此处对代码做了一个小优化，加入了 is_sorted Flag，目的是将算法的最佳时间复杂度优化为 O(n)，即当原输入序列就是排序好的情况下，该算法的时间复杂度就是 O(n)。
选择排序是一种简单直观的排序算法，无论什么数据进去都是 $O(n^2)$ 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
/**
* 选择排序
* @param arr
* @return arr
*/
public static int[] selectionSort(int[] arr) {
for (int i = 0; i 插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用 in-place 排序（即只需用到 $O(1)$ 的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。
/**
* 插入排序
* @param arr
* @return arr
*/
public static int[] insertionSort(int[] arr) {
for (int i = 1; i = 0 && current 希尔排序是希尔 (Donald Shell) 于 1959 年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为递减增量排序算法，同时该算法是冲破 $O(n^2)$ 的第一批算法之一。
希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录 “基本有序” 时，再对全体记录进行依次直接插入排序。
我们来看下希尔排序的基本步骤，在此我们选择增量 $gap=length/2$，缩小增量继续以 $gap = gap/2$ 的方式，这种增量选择我们可以用一个序列来表示，$lbrace frac{n}{2}, frac{(n/2)}{2}, dots, 1 rbrace$，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
/**
* 希尔排序
*
* @param arr
* @return arr
*/
public static int[] shellSort(int[] arr) {
int n = arr.length;
int gap = n / 2;
while (gap > 0) {
for (int i = gap; i = 0 && arr[preIndex] > current) {
arr[preIndex + gap] = arr[preIndex];
preIndex -= gap;
}
arr[preIndex + gap] = current;
}
gap /= 2;
}
return arr;
}
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法 (Divide and Conquer) 的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为 2 - 路归并。
和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 $O(nlogn)$ 的时间复杂度。代价是需要额外的内存空间。
归并排序算法是一个递归过程，边界条件为当输入序列仅有一个元素时，直接返回，具体过程如下：
/**
* 归并排序
*
* @param arr
* @return arr
*/
public static int[] mergeSort(int[] arr) {
if (arr.length 快速排序用到了分治思想，同样的还有归并排序。乍看起来快速排序和归并排序非常相似，都是将问题变小，先排序子串，最后合并。不同的是快速排序在划分子问题的时候经过多一步处理，将划分的两组数据划分为一大一小，这样在最后合并的时候就不必像归并排序那样再进行比较。但也正因为如此，划分的不定性使得快速排序的时间复杂度并不稳定。
快速排序的基本思想：通过一趟排序将待排序列分隔成独立的两部分，其中一部分记录的元素均比另一部分的元素小，则可分别对这两部分子序列继续进行排序，以达到整个序列有序。
快速排序使用 分治法（Divide and conquer）策略来把一个序列分为较小和较大的 2 个子序列，然后递归地排序两个子序列。具体算法描述如下：
pivot)：选择不同位置的中心元素，快速排序就有不同的变体，比如可以选择：第一个元素、最后一个元素以及左端、右端和中心位置上的三个元素的中值作为中心元素
public static int partition(int[] array, int low, int high) {
// 取最后一个元素作为中心元素
int pivot = array[high];
// 定义指向比中心元素大的指针，首先指向第一个元素
int pointer = low;
// 遍历数组中的所有元素，将比中心元素大的放在右边，比中心元素小的放在左边
for (int i = low; i 排序过程的结果如下：
[6, 72, 113, 11, 23]
[6, 72, 113, 11, 23]
[6, 72, 113, 11, 23]
[6, 11, 113, 72, 23]
[6, 11, 23, 72, 113]
[6, 11, 23, 72, 113]
排序后的结果
[6, 11, 23, 72, 113]
从这个排序结果我们可以知道整个排序过程。
由于可能在数组已经有序或基本有序的情况下，最差的时间复杂度。为了避免最坏情况发生，可以通过随机选择基准元素或者使用三数取中法等策略来提高快速排序的性能；或者可以先使用洗牌算法shuffle，将数据打乱。
堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子结点的值总是小于（或者大于）它的父节点。
// Global variable that records the length of an array;
static int heapLen;
/**
* Swap the two elements of an array
* @param arr
* @param i
* @param j
*/
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
/**
* Build Max Heap
* @param arr
*/
private static void buildMaxHeap(int[] arr) {
for (int i = arr.length / 2 - 1; i >= 0; i--) {
heapify(arr, i);
}
}
/**
* Adjust it to the maximum heap
* @param arr
* @param i
*/
private static void heapify(int[] arr, int i) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int largest = i;
if (right arr[largest]) {
largest = right;
}
if (left arr[largest]) {
largest = left;
}
if (largest != i) {
swap(arr, largest, i);
heapify(arr, largest);
}
}
/**
* Heap Sort
* @param arr
* @return
*/
public static int[] heapSort(int[] arr) {
// index at the end of the heap
heapLen = arr.length;
// build MaxHeap
buildMaxHeap(arr);
for (int i = arr.length - 1; i > 0; i--) {
// Move the top of the heap to the tail of the heap in turn
swap(arr, 0, i);
heapLen -= 1;
heapify(arr, 0);
}
return arr;
}
计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
计数排序 (Counting sort) 是一种稳定的排序算法。计数排序使用一个额外的数组 C，其中第 i 个元素是待排序数组 A 中值等于 i 的元素的个数。然后根据数组 C 来将 A 中的元素排到正确的位置。它只能对整数进行排序。
max、最小值 min；C，其长度是 max-min+1，其元素默认值都为 0；A 中的元素 A[i]，以 A[i] - min 作为 C 数组的索引，以 A[i] 的值在 A 中元素出现次数作为 C[A[i] - min] 的值；C 数组变形，新元素的值是该元素与前一个元素值的和，即当 i>1 时 C[i] = C[i] + C[i-1]；R，长度和原始数组一样。A 中的元素 A[i]，使用 A[i] 减去最小值 min 作为索引，在计数数组 C 中找到对应的值 C[A[i] - min]，C[A[i] - min] - 1 就是 A[i] 在结果数组 R 中的位置，做完上述这些操作，将 count[A[i] - min] 减小 1。
/**
* Gets the maximum and minimum values in the array
*
* @param arr
* @return
*/
private static int[] getMinAndMax(int[] arr) {
int maxValue = arr[0];
int minValue = arr[0];
for (int i = 0; i maxValue) {
maxValue = arr[i];
} else if (arr[i] = 0; i--) {
int idx = countArr[arr[i] - minValue] - 1;
result[idx] = arr[i];
countArr[arr[i] - minValue] -= 1;
}
return result;
}
当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 $O(n+k)$。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组 C 的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上 1），这使得计数排序对于数据范围很大的数组，需要大量额外内存空间。
O(k)当数据范围很大或包含负数时，标准计数排序可能面临问题，可以进行如下优化：
public static void countingSortForLargeRange(int[] arr) {
// 找出数组中的最大值和最小值
int max = arr[0], min = arr[0];
for (int i = 1; i max) {
max = arr[i];
}
if (arr[i] arr.length * 100) {
// 这里可以调用其他排序算法，如快速排序
Arrays.sort(arr);
return;
}
// 正常的计数排序逻辑
// ...
}
当只需要排序结果、不需要保持稳定性时，可以省略输出数组，直接更新原数组：
public static void countingSortInPlace(int[] arr) {
// 找出最大值和最小值
int max = arr[0], min = arr[0];
for (int i = 1; i 0) {
arr[index++] = i + min;
count[i]--;
}
}
}
桶排序是一种分配式排序算法，将元素分到有限数量的桶里，每个桶再单独排序（比如用插入排序），最后依次把各个桶中的元素取出来即完成排序。
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：
桶排序的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行。
/**
* Gets the maximum and minimum values in the array
* @param arr
* @return
*/
private static int[] getMinAndMax(List arr) {
int maxValue = arr.get(0);
int minValue = arr.get(0);
for (int i : arr) {
if (i > maxValue) {
maxValue = i;
} else if (i bucketSort(List arr, int bucket_size) {
if (arr.size() > buckets = new ArrayList();
for (int i = 0; i ());
}
for (int element : arr) {
int idx = (element - minValue) / bucket_size;
buckets.get(idx).add(element);
}
for (int i = 0; i 1) {
buckets.set(i, sort(buckets.get(i), bucket_size / 2));
}
}
ArrayList result = new ArrayList();
for (List bucket : buckets) {
for (int element : bucket) {
result.add(element);
}
}
return result;
}
基数排序也是非比较的排序算法，对元素中的每一位数字进行排序，从最低位开始排序，复杂度为 $O(n×k)$，$n$ 为数组长度，$k$ 为数组中元素的最大的位数；
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。
A 为原始数组，从最低位开始取每个位组成 radix 数组；radix 进行计数排序（利用计数排序适用于小范围数的特点）；radix 依次赋值给原数组；
/**
* Radix Sort
*
* @param arr
* @return
*/
public static int[] radixSort(int[] arr) {
if (arr.length maxValue) {
maxValue = element;
}
}
while (maxValue / 10 != 0) {
maxValue = maxValue / 10;
N += 1;
}
for (int i = 0; i > radix = new ArrayList();
for (int k = 0; k ());
}
for (int element : arr) {
int idx = (element / (int) Math.pow(10, i)) % 10;
radix.get(idx).add(element);
}
int idx = 0;
for (List l : radix) {
for (int n : l) {
arr[idx++] = n;
}
}
}
return arr;
}
基数排序 vs 计数排序 vs 桶排序
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top
登录查看全部
参与评论
手机查看
返回顶部