排序算法简介
一、冒泡排序
冒泡排序小结 (关于此排序更详细的优化看前面的C语言版)
1）一共进行数组的大小 -1 次的循环
2）每一趟排序的次数在逐渐的减少
3）如果发现在某趟排序中，没有发生一次交换，可以提前结束冒泡排序(优化)。
/**
* @param arr 冒泡排序
*/
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
boolean flag = false;
//第一趟排序，就是将最大的数排在最后
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr,j,j + 1);
flag = true;
}
}
if (!flag) {// 在一趟排序中，一次交换都没有发生
break;
}
}
}二、选择排序
选择是排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依次规定交换位置后达到排序的目的。
选择排序的思路图解
选择排序是不稳定的，因为元素交换时有可能改变相等值的先后顺序
public class SelectSort {
public static void main(String[] args) {
int[] arr = { 101, 34, 119, 1 };
System.out.println("排序前");
selectSort(arr);
System.out.println("排序后");
System.out.println(Arrays.toString(arr));
}
// 选择排序
public static void selectSort(int[] arr) {// 时间复杂度O(n^2)
// 使用逐步推导的公式来，讲解选择排序
// 第1轮
// 原始的数组：101，34，119，1
// 第一轮排序：1，34，119，101
// 算法 先简单 -->> 做复杂，就是可以把一个复杂的算法，拆分成简单的问题->>逐步解决
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
int min = arr[i];
for (int j = i + 1; j < arr.length; j++) {
if (min > arr[j]) {// 说明假定的最小值，并不是最小
min = arr[j];
minIndex = j;// 重置minIndex
}
}
// 将最小值，放在arr[0],即交换
if (minIndex != i) {
arr[minIndex] = arr[i];
arr[i] = min;
}
}
}
}三、插入排序
插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。
在近乎有序的数据测试中，插入排序的性能好
极端情况下，当集合是一个完全有序的集合，插入排序内层循环一次都不走~~~
插入排序变为O(N)；因此，插入排序经常作为高阶排序算法的优化手段之一
插入排序是稳定的；arr[j] >= arr[j – 1]就停止了；相等的元素不会交换顺序，arr[j] < arr[j – 1]才交换
public class InsertSort {
public static void main(String[] args) {
int[] arr = { 101, 34, 119, 1 };
insertSort(arr);
}
// 插入排序
public static void insertSort(int[] arr) {
int insertVal = 0;
int insertIndex = 0;// 代码规范：定义写在外面
for (int i = 1; i < arr.length; i++) {
// 定义待插入的数
insertVal = arr[i];
insertIndex = i - 1;// 即arr[1]的前面这个数的下标
// 给insertVal找到插入的位置
// 说明
// 1.insertIndex >= 0 保证在给insertVal找插入位置，不越界
// 2.insertVal < arr[insertIndex]待插入的数，还没有找到插入位置
// 3.就需要将arr[insertIndex]后移
while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
arr[insertIndex + 1] = arr[insertIndex];// arr[insertIndex]
insertIndex--;
}
// 当退出while循环时，说明插入的位置找到，insertIndex + 1
// 判断是否需要赋值
if (insertIndex + 1 != i) {
arr[insertIndex + 1] = insertVal;
}
System.out.println("第" + (i) + "轮插入");
System.out.println(Arrays.toString(arr));
}
}
}插入排序和选择排序最大的不同在于：当插入排序当前遍历的元素 > 前驱元素时，此时可以提前结束内层循环
四、希尔排序
希尔排序是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。
算法基本思想
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止
算法示意图
希尔排序时，对有序序列在插入时采用交换法。
希尔排序时，对有序序列在插入时采用移动法。(快很多)
public class ShellSort {
public static void main(String[] args) {
int[] arr = { 8, 9, 1, 7, 2, 3, 5, 4, 6, 0 };
// shellSort(arr);// 交换式
shellSort2(arr);// 移位式
}
// 使用逐步推导的方式来编写希尔排序
// 希尔排序时，对有序序列在插入时采用交换法
// 思路(算法) ==> 代码
public static void shellSort(int[] arr) {
int temp = 0;
int count = 0;
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < arr.length; i++) {
// 遍历各组中所有的元素(共5组，每组有2个元素)，步长5
for (int j = i - gap; j >= 0; j -= gap) {
// 如果当前元素大于加上步长后的那个元素，说明交换
if (arr[j] > arr[j + gap]) {
temp = arr[j];
arr[j] = arr[j + gap];
arr[j + gap] = temp;
}
}
}
}
System.out.println("希尔排序第" + (++count) + "轮后=" + Arrays.toString(arr));
}
// 对交换式的希尔排序进行优化 -> 移位法
public static void shellSort2(int[] arr) {
// 增量gap,并逐步的缩小增量
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
// 从第gap个元素，逐个对其所在的组进行直接插入排序
for (int i = gap; i < arr.length; i++) {
int j = i;
int temp = arr[j];
if (arr[j] < arr[j - gap]) {
while (j - gap >= 0 && temp < arr[j - gap]) {
// 移动
arr[j] = arr[j - gap];
j -= gap;
}
// 当退出while后，就给temp找到插入的位置
arr[j] = temp;
}
}
}
System.out.println("希尔排序第轮后=" + Arrays.toString(arr));
}
}每次取一个gap,将原数组按照gap分组，组内使用插入排序
直到gap = 1时，整个数组已经接近有序，最终直接插入排序一下即可。
（希尔排序代码）j – gap >= 0：说明前面还有距离相同的元素没有判断
（插入排序代码）j > 0 –>> j – 1 >= 0
所以，gap == 1时，希尔排序和插入排序就是一码事！！！
希尔排序算法不稳定
五、快速排序
public class QuickSort {
public static void main(String[] args) {
int[] arr = { -9, 78, 0, 23, -567, 70 };
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr, int left, int right) {
int l = left;// 左下标
int r = right;// 右下标
// pivot 中轴值
int pivot = arr[(left + right) / 2];
int temp = 0;// 临时变量，作为交换时使用
// while循环的目的是让比pivot值小的放到左边
// 比pivot值大的放到右边
while (l < r) {
// 在pivot的左边一直找，找到大于等于pivot值，才退出
while (arr[l] < pivot) {
l += 1;
}
// 在pivot的右边一直找，找到小于等于pivot值，才退出
while (arr[r] > pivot) {
r -= 1;
}
if (l >= r) {
break;
}
// 交换
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
// 如果交换完后，发现这个arr[l] == pivot值 相等r--,前移
if (arr[l] == pivot) {
r -= 1;
}
// 如果交换完后，发现这个arr[r] == pivot值 相等l++,后移
if (arr[r] == pivot) {
l += 1;
}
}
// 如果l == r,必须是l++,r--,否则会出现栈溢出
if (l == r) {
l += 1;
r -= 1;
}
// 向左递归
if (left < r) {
quickSort(arr, left, r);
}
// 向右递归
if (right > l) {
quickSort(arr, l, right);
}
}
}六、归并排序
public class MergetSort {
public static void main(String[] args) {
int arr[] = { 8, 4, 5, 7, 1, 3, 6, 2 };
int temp[] = new int[arr.length];// 归并排序需要一个额外空间
mergeSort(arr, 0, arr.length - 1, temp);
System.out.println("归并排序后=" + Arrays.toString(arr));
}
// 分+合方法
public static void mergeSort(int[] arr, int left, int right, int[] temp) {
if (left < right) {
int mid = (left + right) / 2;// 中间索引
// 向左递归进行分解
mergeSort(arr, left, mid, temp);
// 向右递归进行分解
mergeSort(arr, mid + 1, right, temp);
// 合并
merge(arr, left, mid, right, temp);
}
}
// 合并的方法
/**
* @param arr 排序的原始数组
* @param left 左边有序序列的初始索引
* @param mid 中间索引
* @param right 右边索引
* @param temp 做中转的数组
*/
public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
int i = left;// 初始化，左边有序序列的初始索引
int j = mid + 1;// 初始化j,右边有序序列的初始索引
int t = 0;// 指向temp数组的当前索引
// (一)
// 先把左右两边(有序)的数组按照规则填充到temp数组
// 直到左右两边的有序序列，有一边处理完毕为止
while (i <= mid && j <= right) {// 继续
// 如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素
// 即将左边的当前元素，填充到temp数组
// 然后t++,i++
if (arr[i] <= arr[j]) {
temp[t] = arr[i];
t += 1;
i += 1;
} else {// 反之，将右边有序序列的当前元素，填充到temp数组
temp[t] = arr[j];
t += 1;
j += 1;
}
}
// (二)
// 把有剩余数据的一边的数据依次全部填充到temp
while (i <= mid) {// 左边的有序序列还有剩余的元素，就全部填充到temp
temp[t] = arr[i];
t += 1;
i += 1;
}
while (j <= right) {// 右边的有序序列还有剩余的元素，就全部填充到temp
temp[t] = arr[j];
t += 1;
j += 1;
}
// (三)
// 将temp数组的元素拷贝到arr
// 注意：并不是每次都拷贝所有
t = 0;
int tempLeft = left;
// 第一次合并tempLeft = 0,right = 1// tempLeft = 2 right = 3//tempLeft = 0 right = 3
// 最后一次 tempLeft = 0 right = 7
System.out.println("tempLeft=" + tempLeft + " right=" + right);//帮助理解合并过程，不是算法必要步骤
while (tempLeft <= right) {
arr[tempLeft] = temp[t];
t += 1;
tempLeft += 1;
}
}
}归并排序是一个稳定的nlogn排序算法
此处的稳定指的是时间复杂度稳定且归并排序也是一个稳定性排序算法
时间复杂度稳定：无论集合中的元素如何变化，归并排序的时间复杂度一直都是nlogn,不会退化为O(n^2)
归并排序的两点优化：
1.当左右两个子区间走完子函数后，左右两个区间已经有序了；如果此时arr[mid] < arr[mid + 1]
arr[mid]已经是左区间的最大值；arr[mid + 1]已经是右区间的最小值 => 整个区间已经有序了，没必要再执行merge过程
2.在小区间上，可以直接俄使用插入排序来优化，没必要元素一致拆分到1位置；r – l <= 15,使用插入排序性能是很好的。可以减少归并的递归次数
七、桶排序
桶排序图解
public class RadixSort {
public static void main(String[] args) {
int arr[] = { 53, 3, 542, 748, 14, 214 };
radixSort(arr);
}
// 基数排序方法
public static void radixSort(int[] arr) {
// 1. 得到数组中最大的数的位数
int max = arr[0];// 假设第一数就是最大数
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
// 得到最大数是几位数
int maxLength = (max + "").length();// 加上空串，变成字符串，再求长度
// 定义一个二维数组，表示10个桶，每个桶就是一个一维数组
// 说明
// 1.二维数组包含10个一维数组
// 2.为了防止在放入数的时候，数据溢出，则每个一维数组(桶)，大小定为arr.length
// 3.很明确，基数排序是使用空间换时间的经典算法
int[][] bucket = new int[10][arr.length];
// 为了记录每个桶中，实际存放了多少个数据，定义一个一维数组来记录各个桶的每次放入的数据个数
// 比如：bucketElementCounts[0],记录的就是bucket[0]桶的放入数据个数
int[] bucketElementCounts = new int[10];
// 针对每个元素的对应位进行排序处理；第一次是个位，第二次是十位，第三次是百位...
for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
for (int j = 0; j < arr.length; j++) {
// 取出每个元素的个位的值
int digitOfElement = arr[j] / n % 10;
// 放入到对应的桶中
bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
bucketElementCounts[digitOfElement]++;
}
// 按照这个桶的顺序(一维数组的下标依次取出数据，放入到原来数组)
int index = 0;
// 遍历每一个桶，并将桶中的数据，放入到原数组
for (int k = 0; k < bucketElementCounts.length; k++) {
// 如果桶中，有数据，我们才放入到原数组
if (bucketElementCounts[k] != 0) {
// 循环该桶即第k个桶(即第k个一维数组)，放入
for (int l = 0; l < bucketElementCounts[k]; l++) {
// 取出元素放入到arr
arr[index++] = bucket[k][l];
}
}
// 每一轮处理后，需要将每个bucketElementCounts[k] = 0 !!!!!!!!!!
bucketElementCounts[k] = 0;
}
System.out.println("第" + (i + 1) + "轮，对个位的排序处理 arr =" + Arrays.toString(arr));
}
}
}
总结
桶排序、基数排序、计数排序对于数据集合的要求非常高，只能在特定的场合下使用
稳定性算法的用途：
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/110946.html
