????欢迎大家观看AUGENSTERN_dc的文章(o゜▽゜)o☆✨✨
????感谢各位读者在百忙之中抽出时间来垂阅我的文章，我会尽我所能向的大家分享我的知识和经验????
????希望我们在一篇篇的文章中能够共同进步！！！
????个人主页：AUGENSTERN_dc
????个人专栏：C语言 | Java | 数据结构| 算法
⭐个人格言：
一重山有一重山的错落，我有我的平仄
一笔锋有一笔锋的着墨，我有我的舍得
目录
1. 排序的概念及应用：
1.1 概念：
1.2 排序的运用:
2. 排序算法:
3. 选择排序:
3.1 简单选择排序:
3.1.1 代码:
3.1.2 时间复杂度:
3.2 选择排序:
3.2.1 代码:
3.2.2 时间复杂度:
3.3 堆排序:
3.3.1 代码:
3.3.2 堆排序的特性:
4. 插入排序:
4.1 直接插入排序:
4.1.1 代码:
4.1.2 直接插入排序的特性:
4.2 希尔排序:
4.2.1 代码:
4.2.2 希尔排序的特性:
5. 交换排序:
5.1 冒泡排序:
5.1.1 代码:
5.1.2 冒泡排序特性:
5.2 快速排序:
5.2.1 简单的快速排序:
5.2.1.1 Hoare法:
5.2.1.2 挖坑法:
5.2.1.3 前后指针法:
5.2.1.4 简单快排的实现:
5.2.1.5 代码:
5.2.2 快速排序的优化:
5.2.2.1 改变基准值:
5.2.2.1.1 代码:
5.2.2.2 在快排中使用插入排序:
5.2.3: 优化后快速排序整体代码:
5.2.4.1 代码:
5.2.4 快速排序的特性:
6. 归并排序:
6.1 代码:
6.2 非递归实现归并排序:
6.3 归并排序的特性:
6.4 海量数据的排序问题:
7. 基于比较的排序算法的总结:
8. 计数排序:
8.1 代码:
8.2 计数排序的特性:
9. 基数排序:
9.1 代码:
9.2 基数排序的特性
10. 桶排序:
10.1 代码:
10.2 桶排序的特性:
11. 排序测试:
11.1 生成升序,降序,随机三种整形数组
11.2 生成测试用例:
1. 排序的概念及应用：
1.1 概念：
所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性： 假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
如下图：
在排序之前,红色的4在蓝色的4之前, 若排序之后,红色4依然在蓝色的4之前,那么我们说这个排序是稳定的,若红色4在排序之后在蓝色的4之后,则我们说这个排序是不稳定的;
内部排序: 数据元素全部放在内存中的排序。
外部排序: 数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
1.2 排序的运用:
例如我们的高校排名, 就是一个典型的排序的运用,
我们可以根据不同的属性去进行高校排名的比较;
2. 排序算法:
(在接下来的排序算法中,我们默认排序是升序的,也就是从小到大排序!!!!!)
3. 选择排序:
3.1 简单选择排序:
首先我们先介绍比较简单的选择排序:
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。
选择排序是不稳定的排序方法。
首先我们先写简单的选择排序:
假设给定一个整形数组,我们需要对整个数组进行排序,我们不妨先遍历一次数组找到这个数组中的最小值,再将其放在数组的第一个元素上,继续进行第二次遍历,找到除了第一个元素之外的最小的元素,放在数组的第二个元素上,依此类推,直到需要排序的元素个数为0;
3.1.1 代码:
private static void swap(int[] array, int x, int y) {
int tmp = array[x];
array[x] = array[y];
array[y] = tmp;
}public static void selectSort(int[] array) {
int minIndex = 0; //记录最小元素的下标
for (int i = 0; i < array.length; i++) { //对数组进行遍历,本次遍历是控制遍历的次数;
for (int j = i + 1; j < array.length; j++) { //本次遍历是找到数组中的最小值
if (array[minIndex] > array[j]) {
minIndex = j; //将最小值的下标赋给minIndex
}
}
swap(array, minIndex, i); //交换下标为i的元素和下标为minIndex的元素
}
}3.1.2 时间复杂度:
不难看出,该时间复杂度为O(n + n - 1 + n - 2 + n - 3 + .......... + 3 + 2 + 1) = O(n * (n + 1) / 2) =
O(n ^ 2);
3.2 选择排序:
上述的简单选择排序仅仅只是找到数组中的最小值,然后和下标为 i 的元素进行交换,这次我们在每次遍历数组的时候,找到需要排序的元素中的最大值和最小值,分别将其和需要排序的元素的第一个和最后一个进行交换,这样效率会高很多:
3.2.1 代码:
public static void selectSortPlus(int[] array) {
int left = 0; //需要排序的元素的第一个元素的下标
int right = array.length - 1; //需要排序的元素的最后一个元素的下标
while (left < right) { //只要left < right,就说明还存在一个以上的需要排序的元素
int maxIndex = left;
int minIndex = left;
for (int i = left + 1; i <= right; i++) { //这次循环是为了找到最大值下标和最小值的下标
if (array[maxIndex] < array[i]) {
maxIndex = i;
}
if (array[minIndex] > array[i]) {
minIndex = i;
}
}
swap(array, left, minIndex); //交换left和最小值
if (maxIndex == left) { //若left元素就是最大值,则在上一行代码left元素就被交换了,我们则需要将maxIndex重置为minIndxe
maxIndex = minIndex;
}
swap(array, right, maxIndex); //再交换right位置的元素和maxIndex位置的元素
right--; //再将需要排序的范围减小
left++;
}
}3.2.2 时间复杂度:
此时的时间复杂度依然是O(n ^ 2)
但是这次的选择排序会比上一个简单选择排序效率更高,我们会在后面进行测试;
3.3 堆排序:
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
堆排序的步骤一共有三个:
< 1 > 首先将所需要排序的元素构建成一个堆
< 2 > 再将堆顶元素弹出
< 3 > 最后调整堆,使其依然是一给大根堆,继续执行1 2 3操作,直到堆中需要排序的元素只剩一个
3.3.1 代码:
public static void heapSort(int[] array) {
createHeap(array); //首先调用创建堆的方法
int len = array.length; //len是数组的长度
while (len > 0){
swap(array, 0, len - 1); //将堆顶元素放到数组的最末尾
shiftdown(array, 0, --len); //向下调整整个堆,使其依然是一个大根堆,并将len--,防止已经排序的元素被再次调动
}
}
private static void createHeap(int[] array) {
int parent = (array.length - 2) / 2;
while (parent >= 0) {
shiftdown(array, parent, array.length); //利用向下调整来建堆
parent--;
}
}
private static void shiftdown(int[] array, int parent, int len) {
int child = parent * 2 + 1; //孩子节点的下标
while (child < len) { //只要孩子节点的下标 < len说明向下调整还未结束
if (child + 1 < len) { //保证child下标的元素是左右孩子中最大的
child = array[child] > array[child + 1] ? child : child + 1;
}
if (array[child] > array[parent]) { //如果孩子节点大于双亲节点就交换
swap(array, child, parent);
parent = child;
child = parent * 2 + 1;
} else {
break; //如果不大于则跳出循环
}
}
}3.3.2 堆排序的特性:
< 1 > 堆排序使用堆来选数，效率就高了很多,例如topK问题;
< 2 > 时间复杂度：在堆排序中,向下调整的时间复杂度就是树的高度,也就是logn,最坏一共会调整n次
故其时间复杂度为O(n * logn)
< 3 > 空间复杂度：O(1)
< 4 > 稳定性：不稳定
4. 插入排序:
4.1 直接插入排序:
直接插入排序（Straight Insertion Sort）是一种最简单的排序方法，其基本操作是将一条记录插入到已排好的有序表中，从而得到一个新的、记录数量增1的有序表。
我们打扑克牌时,抓手牌的时候,一般用的就是直接插入排序
每当我们摸了一张牌,我们就会比较这张牌和手中的牌的大小,进行插入操作;
直接插入排序也是如此:
< 1 > 我们依次取待排序的数组中的第一个元素与已排好数组的元素进行比较(若已排好数组的元素个数为0,则直接进行插入)
< 2 > 将待排序的数组的第一个元素与已排序的数组的元素进行比较,从最后一个元素开始比较
< 3 > 若该元素比某一个已排序的数组的元素大,则继续向后比较,若比其小,则将该元素插入到这个元素之前,并跳出循环
4.1.1 代码:
public static void insertSort(int[] array) {
for (int i = 1; i < array.length; i++) {
int tmp = array[i];
int j = i - 1;
for (; j >= 0; j--) {
if (array[j] > tmp) {
array[j + 1] = array[j];
} else {
break;
}
}
array[j + 1] = tmp;
}
}
4.1.2 直接插入排序的特性:
< 1 > 元素集合越接近有序，直接插入排序算法的时间效率越高
< 2 > 时间复杂度：O(N^2)
< 3 > 空间复杂度：O(1)
< 4 > 稳定性：稳定
4.2 希尔排序:
希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。
我们刚刚提到,直接插入排序中的元素集合越接近有序,直接插入排序算法的时间效率便越高,假设我们有一百个数据需要排序,如果使用直接插入排序进行排序处理的话,效率比较低,但是如果我们将这100个数据分成十组,将每一组按照直接插入排序的方法进行排序后,这100个数据的就更加接近有序了,再对这一百个数据进行直接插入排序的效率会比一次性将100个数据进行直接插入排序的效率高很多,这种方法就叫希尔排序;
希尔排序主要是分一下几个步骤:
< 1 > 首先将待排序的集合分成k个集合
< 2 > 对这几个集合分别使用直接插入排序
< 3 > 再将这写小集合合并成一个更大的集合
< 4 > 继续对这些集合使用直接插入排序
< 5 > 直到k 的值为1,也就是最后合并成一个大集合为止,此时的集合中的元素已经趋于有序,使用直接插入排序的效率会很高
注意!!!:
4.2.1 代码:
public static void shellSort(int[] array) {
int gap = array.length;
while (gap > 1) {
gap = gap / 3 + 1;
shell(array, gap, array.length - 1);
}
}
private static void shell(int[] array, int gap, int len) {
for (int i = gap; i < array.length; i++) {
int tmp = array[i];
int j = i - gap;
for (; j >= 0; j -= gap) {
if (array[j] > tmp) {
array[j + gap] = array[j];
} else {
break;
}
}
array[j + gap] = tmp;
}
}希尔排序的代码实现,实际上就是对直接插入排序的部分修改;
4.2.2 希尔排序的特性:
< 1 > 希尔排序是对直接插入排序的优化。
< 2 > 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快,这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
< 3 > 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定;
< 4 > 稳定性：不稳定
5. 交换排序:
5.1 冒泡排序:
冒泡排序是一种十分简单的排序,是大多数学编程的同学接触到第一种排序算法;
冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法,它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行，直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
在这里我就不做过多的介绍了:
5.1.1 代码:
public static void bubbleSort(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
boolean flag = true;
for (int j = 0; j < array.length - 1 - i; j++) {
if (array[j] > array[j + 1]) {
swap(array, j, j + 1);
flag = false;
}
}
if (flag) {
return;
}
}
}5.1.2 冒泡排序特性:
< 1 > 冒泡排序是一种非常容易理解的排序
< 2 > 时间复杂度：O(N^2)
< 3 > 空间复杂度：O(1)
< 4 > 稳定性：稳定
5.2 快速排序:
5.2.1 简单的快速排序:
快速排序(Quick Sort)是一种高效的排序算法，它通过分治法将待排序的数据分为两部分，并对这两部分递归地进行排序，以实现整个序列的有序。
- 算法思路: 快速排序的核心在于多次比较和交换，它首先选择一个元素作为基准值，然后将待排序的元素分为两部分，一部分的元素小于基准值，另一部分的元素大于基准值。接着对这两部分进行快速排序，以此类推，直到整个序列有序。1234
- 算法步骤: 首先设置一个基准值，通常选择第一个元素作为基准；然后通过遍历整个序列，将待排序的元素与基准值进行比较，如果元素小于基准值，则将其移动到左边；如果元素大于基准值，则将其移动到右边；重复这个过程，直到所有元素都各归其位，最后对左右两个子序列分别进行快速排序，以实现整个序列的有序。
将区间按照基准值划分为左右两半部分的常见方式有三种,我们先讲述第一种
5.2.1.1 Hoare法:
< 1 > 首先以第一个元素作为基准值
< 2 > 设置两个指针,分别指向待排序数组(除基准值)的最左边和最右边
< 3 > 先将最右边的指针向左遍历,直到找到比基准值小的元素为止
< 4 > 再将最左边的指针向右遍历,直到找到比基准值大的元素为止
< 5 > 交换左右指针指向的元素
< 6 > 最后狡猾left和i所对应的元素,返回left
private static int getPivotIndexHoare(int[] array, int left, int right) {
int tmp = array[left];
int i = left;
while (left < right) {
while (left < right && array[right] >= tmp) { //找到比基准值小的元素或left和right相遇则停止
right--;
}
if (left >= right) { //若相遇则跳出循环
break;
}
while (left < right && array[left] <= tmp) { //找到比基准值大的元素或left和right相遇则停止
left++;
}
if (left >= right) {
break;
}
swap(array, right, left);
}
swap(array, left, i);
return left; //返回left的值,也就是当前基准值的下标
}这里我们需要注意一个细节: 一定要right先遍历数组,找到比基准值小的元素
因为我们最后停止遍历时,left和right一定是相遇了,我们就需要将left所对应的元素和基准值进行交换,如果我们让left先进行遍历的话,倘若left已经找到了比基准值大的元素了,而right没有找到比基准值小的元素,而和left相遇了,此时left下标对应的元素是比基准值大的,若将他们进行交换,则会导致基准值的左边的元素并不是全都比基准值小的,故我们需先让right进行遍历;
5.2.1.2 挖坑法:
思路如下:
< 1 > 首先我们用一个变量将基准值存下来
< 2 > 让right先遍历数组,找到比基准值小的元素
< 3 >交换left和right的值
< 4 > 让left遍历数组,找到比基准值大的元素
< 5 > 交换left和right的值
< 6 > 循环结束后,将left的值重置为基准值
private static int getPivotIndexDigHole(int[] array, int left, int right) {
int tmp = array[left]; //用tmp存放基准值
while (left < right) {
while (left < right && array[right] >= tmp) { //找到比基准值小的元素或者left和right相遇则停止
right--;
}
if (left >= right) {
break;
}
array[left] = array[right]; //将right的值赋给left对应的值
while (left < right && array[left] <= tmp) { //找到比基准值大的元素
left++;
}
if (left >= right) {
break;
}
array[right] = array[left]; //将left赋给right的值
}
array[left] = tmp;
return left;
}5.2.1.3 前后指针法:
前后指针法在快速排序中的使用较少,较多使用的是Hoare法和挖坑法;
思路如下:
< 1 > 创建连个指针prev 和 cur,分别指向第一个和第二个元素
< 2 > 先让后面的指针移动一次,并进行判断, 若cur指针的元素小于基准值,则prev先++,再判断prev对应的元素是否 = cur对应的元素
< 3 > 若不等于, 则交换cur对应的元素和prev对应的元素
< 4 > 再让cur向后移动
< 5 > 最后交换prev和left的对应的值
private static int partition(int[] array, int left, int right) {
int prev = left ;
int cur = left+1;
while (cur <= right) {
if(array[cur] < array[left] && array[++prev] != array[cur]) {
swap(array,cur,prev);
}
cur++;
}
swap(array,prev,left);
return prev;
}5.2.1.4 简单快排的实现:
在快排的实现中,我们使用的是较为常见的Hoare法:
< 1 >首先我们需要一个递归的终止条件,也就是当left >= right时,我们需要停止递归;
< 2 > 接下来我们需要找到基准值,在找到基准值的过程中,也就是Hoare法的过程中,我们会把比基准值小的元素放在基准值左边,比基准值大的元素放在基准值的右边
< 3 > 再对基准值的左边和右边递归实现上述操作,直到left >= right 为止
5.2.1.5 代码:
public static void quickSort(int[] array) {
quick(array, 0, array.length - 1);
}
private static void quick(int[] array, int left, int right) {
if (left >= right) {
return;
}
int pivot = getPivotIndexHoare(array, left, right);
quick(array, left, pivot - 1);
quick(array, pivot + 1, right);
}这就是简单的快速排序;
5.2.2 快速排序的优化:
在我们实现算法的时候,我们经常会考虑到最坏情况,也就是数组是降序的时候,如果此时我们需要将该数组排序成升序,用上述的快速排序的代码,我们会发现,效率会十分的低,因为每次将区间按照基准值划分的过程中,基准值都会和最后一个元素进行交换,若把该过程看成一颗二叉树的话,这就像一个单分支树一样,递归的效率十分慢;
所以上述的快速排序还有优化的空间
5.2.2.1 改变基准值:
在一般情况下,我们的基准值会是数组的第一个元素,但是想刚刚我们说的,数组是降序的情况下,基准值只会和最后一个元素进行交换,导致递归的深度达到了n次, 那我们不妨在每次设置基准值的时候,尽量使基准值的大小靠近数组的元素的平均值一点;
我们可以在数组中找到拿到一下三个元素进行比较: 第一个元素, 最后一个元素, 中间的元素
将这三个元素中的中间值拿出来作为基准值,就可以有效避免递归深度过深的情况了
5.2.2.1.1 代码:
private static int getMidIndex(int[] array, int left, int right) {
int mid = left + ((right - left) >>> 1);
if (array[left] > array[right]) {
if (array[mid] > array[left]) {
return left;
} else if (array[mid] < array[right]) {
return right;
} else {
return mid;
}
} else {
if (array[mid] > array[right]) {
return right;
} else if (array[mid] < array[left]) {
return left;
} else {
return mid;
}
}
}5.2.2.2 在快排中使用插入排序:
在上面我们提到,当数组的元素越接近有序的情况下,直接插入排序的效率也就越高,所以,我们可以在快速排序中,当递归到某种程度时,我们不再对剩下的元素进行快速排序,而是选择使用直接插入排序, 效率会比一直用快速排序更高
在我的代码中,我选择在right - left <= 15 时使用直接插入排序
5.2.3: 优化后快速排序整体代码:
public static void quickSort(int[] array) {
quick(array, 0, array.length - 1);
}
private static void quick(int[] array, int left, int right) {
if (left >= right) {
return;
}
if (right - left < 10) {
quickAndInsertSort(array, left, right);
return;
}
int mid = getMidIndex(array, left, right);
swap(array, left, mid);
int pivot = getPivotIndexHoare(array, left, right);
quick(array, left, pivot - 1);
quick(array, pivot + 1, right);
}
private static void quickAndInsertSort(int[] array, int left, int right) {
for (int i = left + 1; i <= right; i++) {
int tmp = array[i];
int j = i - 1;
for (; j >= left; j--) {
if (array[j] > tmp) {
array[j + 1] = array[j];
} else {
break;
}
}
array[j + 1] = tmp;
}
}
private static int getPivotIndexHoare(int[] array, int left, int right) {
int tmp = array[left];
int i = left;
while (left < right) {
while (left < right && array[right] >= tmp) { //找到比基准值小的元素或left和right相遇则停止
right--;
}
if (left >= right) { //若相遇则跳出循环
break;
}
while (left < right && array[left] <= tmp) { //找到比基准值大的元素或left和right相遇则停止
left++;
}
if (left >= right) {
break;
}
swap(array, right, left);
}
swap(array, left, i);
return left; //返回left的值,也就是当前基准值的下标
}
private static int getMidIndex(int[] array, int left, int right) {
int mid = left + ((right - left) >>> 1);
if (array[left] > array[right]) {
if (array[mid] > array[left]) {
return left;
} else if (array[mid] < array[right]) {
return right;
} else {
return mid;
}
} else {
if (array[mid] > array[right]) {
return right;
} else if (array[mid] < array[left]) {
return left;
} else {
return mid;
}
}
}5.2.4 非递归实现快速排序:
在之前的我数据结构专题的文章 栈 中曾讲到过,栈的一个应用就是将递归转化为非递归;
既然快速排序是用递归来实现的,那我们也可以用栈来实现快速排序;
思路和递归实现快排类似,就不再过多解释了;
5.2.4.1 代码:
public static void quickSortNor(int[] array) {
Stack<Integer> stack = new Stack<>();
int left = 0;
int right = array.length - 1;
int pivot = getPivotIndexDigHole(array, left, right);
if (pivot - 1 > left) {
stack.push(pivot - 1);
stack.push(left);
}
if (pivot + 1 < right) {
stack.push(right);
stack.push(pivot + 1);
}
while (!stack.isEmpty()) {
left = stack.pop();
right = stack.pop();
pivot = getPivotIndexDigHole(array, left, right);
if (pivot - 1 > left) {
stack.push(pivot - 1);
stack.push(left);
}
if (pivot + 1 < right) {
stack.push(right);
stack.push(pivot + 1);
}
}
}5.2.4 快速排序的特性:
< 1 > 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
< 2 > 时间复杂度：O(N * logN)
< 3 > 空间复杂度：O(logN)
< 4 > 稳定性：不稳定
6. 归并排序:
归并排序: 是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
归并排序和快速排序有些类似,实现过程简单来说就是两个部分:
< 1 > 将由n个元素组成的序列分成n个子序列
< 2 > 再将n个子序列按照合并两个有序数列的方式进行合并;
具体实现步骤如下:
< 1 > 首先需要递归终止条件,当left >= right时,停止递归
< 2 > 找到数组中的中间位置
< 3 > 将数组分为两个部分, 一部分是第一个元素到中间的元素,第二个部分是中间的元素到最后一个元素
< 4 > 重复实现上述操作
< 5 > 最后对这些子序列进行合并两个有序数组的操作
6.1 代码:
public static void mergeSort(int[] array) {
mergeFunc(array, 0, array.length - 1);
}
private static void mergeFunc(int[] array, int left, int right) {
if (left >= right) {
return;
}
int mid = left + ((right - left) >> 1);
mergeFunc(array, left, mid);
mergeFunc(array, mid + 1, right);
merge(array, left, mid ,right);
}
private static void merge(int[] array, int left, int mid, int right) {
int s1 = left;
int e1 = mid;
int s2 = mid +1;
int e2 = right;
int[] tmp = new int[right - left + 1];
int k = 0;
while (s1 <= e1 && s2 <= e2) {
if (array[s1] <= array[s2]) {
tmp[k++] = array[s1++];
} else {
tmp[k++] = array[s2++];
}
}
while (s1 <= e1) {
tmp[k++] = array[s1++];
}
while (s2 <= e2) {
tmp[k++] = array[s2++];
}
for (int i = 0; i < k ; i++) {
array[i + left] = tmp[i];
}
}6.2 非递归实现归并排序:
该实现依然要使用到栈,操作类似于递归实现,且操作较为简单,就不再过多重述:
public static void mergeSortNor(int[] array) {
int gap = 1;
while (gap < array.length) {
for (int i = 0; i < array.length; i = i + 2 * gap) {
int left = i;
int mid = i + gap - 1;
if (mid >= array.length) {
mid = array.length - 1;
}
int right =i + 2 * gap - 1;
if (right >= array.length) {
right = array.length - 1;
}
merge(array, left, mid, right);
}
gap *= 2;
}
}6.3 归并排序的特性:
< 1 > 归并排序的思考更多的是解决在磁盘中的外排序问题。
< 2 > 时间复杂度：O(N*logN)
< 3 > 空间复杂度：O(N)
< 4 > 稳定性：稳定
6.4 海量数据的排序问题:
外部排序：排序过程需要在磁盘等外部存储进行的排序
前提：内存只有 1G，需要排序的数据有 100G 因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序
< 1 > 先把文件切分成 200 份，每个 512 M
< 2 > 分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以
< 3 > 进行 2路归并，同时对 200 份有序文件做归并过程，最终结果就有序了
7. 基于比较的排序算法的总结:
8. 计数排序:
计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。 当然这是一种牺牲空间换取时间的做法，而且当O(k)＞O(n*log(n))的时候其效率反而不如基于比较的排序;
计数排序的实现十分简单,他类似于我们学的数据结构 哈希表:
< 1 > 首先我们需要算出数组中最大值和最小值的差值k
< 2 > 再创建一个大小为k + 1的数组,其中的值初始化为0;
< 3 > 令原数组中的最小值为min
< 4 > 遍历整个数组,每当遍历到一个数时,将新数组中 该数对应的 值 - min 的下标所对应的值 + 1
< 5 > 遍历完整个数组后,依次遍历新数组的每一个值,并打印 (该值的大小)个的 (该下标 + min)
例如,一个数组{ 7, 8, 10, 5, 5, 6}, 我们创建一个大小为10 - 5 + 1的数组, 遍历第一个元素7, 则新数组的下标为2 的值 + 1,遍历第二个元素8, 则下标为3的值 +1;一直遍历完原数组,则新数组的值为{2,1,1,1,0,1},最后依次打印两次0 + 5, 一次1 + 5, 一次2 + 5, 一次3 + 5, 零次4 + 5, 一次5 + 5;
这就是计数排序;
8.1 代码:
public static void countSort(int[] array) {
int min = array[0];
int max = min;
for (int i = 0; i < array.length; i++) {
if (min > array[i]) {
min = array[i];
}
if (max < array[i]) {
max = array[i];
}
}
count(array, min, max);
}
private static void count(int[] array, int min, int max) {
int range = max - min + 1;
int[] tmpArray = new int[range];
for (int i = 0; i < array.length; i++) {
tmpArray[array[i] - min]++;
}
int index = 0;
for (int i = 0; i < range; i++) {
for (int j = 0; j < tmpArray[i]; j++) {
array[index++] = i + min;
}
}
}8.2 计数排序的特性:
< 1 > 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
< 2 > 时间复杂度：O(MAX(N,范围))
< 3 > 空间复杂度：O(范围)
< 4 > 稳定性：稳定
9. 基数排序:
基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，在某些时候，基数排序法的效率高于其它的稳定性排序法。
9.1 代码:
public static void radixSort(int[] arr) {
int[][] temp = new int[10][arr.length];
int[] counts = new int[10];
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
int maxLength = (max + "").length();
for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
for (int j = 0; j < arr.length; j++) {
int ys = arr[j] / n % 10;
temp[ys][counts[ys]] = arr[j];
counts[ys]++;
}
int index = 0;
for (int k = 0; k < counts.length; k++) {
if (counts[k] != 0) {
for (int l = 0; l < counts[k]; l++) {
arr[index] = temp[k][l];
index++;
}
counts[k] = 0;
}
}
System.out.println(Arrays.toString(arr));
}
}9.2 基数排序的特性
< 1 > 时间复杂度: O(d(n+radix))
< 2 > 空间复杂度: O(n)
< 3 > 稳定性: 稳定
10. 桶排序:
桶排序（Bucket sort）是一种将数组分到有限数量的桶里进行排序的算法，每个桶中的数据元素再进行排序。桶排序的核心思想就是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序，再把每个桶的数据按照顺序依次取出，组成的序列就是有序的了。
所谓的桶,其实就是一个范围,将每个范围中的元素排序完成后,拿出来,就是一个有序的序列了;
10.1 代码:
public static void basket(int array[]) {
int n = array.length;
int bask[][] = new int[10][n];
int index[] = new int[10];
int max = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
max = max > (Integer.toString(array[i]).length()) ? max : (Integer.toString(array[i]).length());
}
String str;
for (int i = max - 1; i >= 0; i--) {
for (int j = 0; j < n; j++) {
str = "";
if (Integer.toString(array[j]).length() < max) {
for (int k = 0; k < max - Integer.toString(array[j]).length(); k++)
str += "0";
}
str += Integer.toString(array[j]);
bask[str.charAt(i) - '0'][index[str.charAt(i) - '0']++] = array[j];
}
int pos = 0;
for (int j = 0; j < 10; j++) {
for (int k = 0; k < index[j]; k++) {
array[pos++] = bask[j][k];
}
}
for (int x = 0; x < 10; x++) index[x] = 0;
}
}10.2 桶排序的特性:
< 1 > 时间复杂度: O(n²)
< 2 > 空间复杂度: O(n+k)
< 3 > 稳定性: 稳定
11. 排序测试:
为了更好的验证排序所耗时间的多少,我们不妨写一个测试用例:
(以下测试用例并没有包含非基于比较的排序算法!!!!)
11.1 生成升序,降序,随机三种整形数组
public static int[] inorder(int n) { //升序数组
int[] array = new int[n];
for (int i = 0; i < n; i++) {
array[i] = i;
}
return array;
}
public static int[] lastorder(int n) { //降序数组
int[] array = new int[n];
for (int i = 0; i < n; i++) {
array[i] = array.length - i;
}
return array;
}
public static int[] initorder(int n) { //随机数组
int[] array = new int[n];
Random random = new Random();
for (int i = 0; i < n; i++) {
array[i] = random.nextInt(n);
}
return array;
}11.2 生成测试用例:
public static void bubbleSortTest(int[] array) {
int[] tmpArray = Arrays.copyOf(array, array.length);
long startTime = System.currentTimeMillis();
Sort.bubbleSort(tmpArray);
long endTime = System.currentTimeMillis();
System.out.println("冒泡排序:" + (endTime - startTime));
}
public static void selectSortTest(int[] array) {
int[] tmpArray = Arrays.copyOf(array, array.length);
long startTime = System.currentTimeMillis();
Sort.selectSort(tmpArray);
long endTime = System.currentTimeMillis();
System.out.println("选择排序:" + (endTime - startTime));
}
public static void selectSortPlusTest(int[] array) {
int[] tmpArray = Arrays.copyOf(array, array.length);
long startTime = System.currentTimeMillis();
Sort.selectSortPlus(tmpArray);
long endTime = System.currentTimeMillis();
System.out.println("加强选择排序:" + (endTime - startTime));
}
public static void insertSortTest(int[] array) {
int[] tmpArray = Arrays.copyOf(array, array.length);
long startTime = System.currentTimeMillis();
Sort.insertSort(tmpArray);
long endTime = System.currentTimeMillis();
System.out.println("插入排序:" + (endTime - startTime));
}
public static void shellSortTest(int[] array) {
int[] tmpArray = Arrays.copyOf(array, array.length);
long startTime = Syst