Java实现八种常用排序算法，你会几个？
沈阳市和平区爱尚职业培训机构
发表于：2022-05-23 16:23:10 23次浏览一、交换排序
所谓交换，就是序列中任意两个元素进行比较，根据比较结果来交换各自在序列中的位置，以此达到排序的目的。
1. 冒泡排序
冒泡排序是一种简单的交换排序算法，以升序排序为例，其核心思想是：
从个元素开始，比较相邻的两个元素。如果个比第二个大，则进行交换。
轮到下一组相邻元素，执行同样的比较操作，再找下一组，直到没有相邻元素可比较为止，此时最后的元素应是大的数。
除了每次排序得到的最后一个元素，对剩余元素重复以上步骤，直到没有任何一对元素需要比较为止。
用 Java 实现的冒泡排序如下
public void bubbleSortOpt(int[] arr) {
if(arr == null) {
throw new NullPoniterException();
}
if(arr.length < 2) {
return;
}
int temp = 0;
for(int i = 0; i < arr.length - 1; i++) {
for(int j = 0; j < arr.length - i - 1; j++) {
if(arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
2. 排序
排序的思想很简单，就是先把待排序的数组拆成左右两个区间，左边都比中间的基准数小，右边都比基准数大。接着左右两边各自再做同样的操作，完成后再拆分再继续，一直到各区间只有一个数为止。
举个例子，现在我要排序 4、9、5、1、2、6 这个数组。一般取位的 4 为基准数，第一次排序的结果是：
2、1、4、5、9、6
可能有人觉得奇怪，2 和 1 交换下位置也能满足条件，为什么 2 在位？这其实由实际的代码实现来决定，并不影响之后的操作。以 4 为分界点，对 2、1、4 和 5、9、6 各自排序，得到：
1、2、4、5、9、6
不用管左边的 1、2、4 了，将 5、9、6 拆成 5 和 9、6，再排序，至此结果为：
1、2、4、5、6、9
为什么把快排划到交换排序的范畴呢？因为元素的移动也是靠交换位置来实现的。算法的实现需要用到递归（拆分区间之后再对每个区间作同样的操作）
用 Java 实现的排序如下
public void quicksort(int[] arr, int start, int end) {
if(start < end) {
// 把数组中的位数字作为基准数
int stard = arr[start];
// 记录需要排序的下标
int low = start;
int high = end;
// 循环找到比基准数大的数和比基准数小的数
while(low < high) {
// 右边的数字比基准数大
while(low < high && arr[high] >= stard) {
high--;
}
// 使用右边的数替换左边的数
arr[low] = arr[high];
// 左边的数字比基准数小
while(low < high && arr[low] <= stard) {
low++;
}
// 使用左边的数替换右边的数
arr[high] = arr[low];
}
// 把标准值赋给下标重合的位置
arr[low] = stard;
// 处理所有小的数字
quickSort(arr, start, low);
// 处理所有大的数字
quickSort(arr, low + 1, end);
}
}二、插入排序
插入排序是一种简单的排序方法，其基本思想是将一个记录插入到已经排好序的有序表中，使得被插入数的序列同样是有序的。按照此法对所有元素进行插入，直到整个序列排为有序的过程。
1. 直接插入排序
直接插入排序就是插入排序的粗暴实现。对于一个序列，选定一个下标，认为在这个下标之前的元素都是有序的。将下标所在的元素插入到其之前的序列中。接着再选取这个下标的后一个元素，继续重复操作。直到最后一个元素完成插入为止。我们一般从序列的第二个元素开始操作。
用 Java 实现的算法如下：
public void insertSort(int[] arr) {
// 遍历所有数字
for(int i = 1; i < arr.length - 1; i++) {
// 当前数字比前一个数字小
if(arr[i] < arr[i - 1]) {
int j;
// 把当前遍历的数字保存起来
int temp = arr[i];
for(j = i - 1; j >= 0 && arr[j] > temp; j--) {
// 前一个数字赋给后一个数字
arr[j + 1] = arr[j];
}
// 把临时变量赋给不满足条件的后一个元素
arr[j + 1] = temp;
}
}
}
2. 希尔排序
某些情况下直接插入排序的效率极低。比如一个已经有序的升序数组，这时再插入一个比最小值还要小的数，也就意味着被插入的数要和数组所有元素比较一次。我们需要对直接插入排序进行改进。
怎么改进呢？前面提过，插入排序对已经排好序的数组操作时，效率很高。因此我们可以试着先将数组变为一个相对有序的数组，然后再做插入排序。
希尔排序能实现这个目的。希尔排序把序列按下标的一定增量（步长）分组，对每组分别使用插入排序。随着增量（步长）减少，一直到一，算法结束，整个序列变为有序。因此希尔排序又称缩小增量排序。
一般来说，初次取序列的一半为增量，以后每次减半，直到增量为一。
用 Java 实现的算法如下：
public void shellSort(int[] arr) {
// gap 为步长，每次减为原来的一半。
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
// 对每一组都执行直接插入排序
for (int i = 0 ;i < gap; i++) {
// 对本组数据执行直接插入排序
for (int j = i + gap; j < arr.length; j += gap) {
// 如果 a[j] < a[j-gap]，则寻找 a[j] 位置，并将后面数据的位置都后移
if (arr[j] < arr[j - gap]) {
int k;
int temp = arr[j];
for (k = j - gap; k >= 0 && arr[k] > temp; k -= gap) {
arr[k + gap] = arr[k];
}
arr[k + gap] = temp;
}
}
}
}
}
三、选择排序
选择排序是一种简单直观的排序算法，首先在未排序序列中找到小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
1. 简单选择排序
选择排序思想的暴力实现，每一趟从未排序的区间找到一个小元素，并放到位，直到全部区间有序为止。
用 Java 实现的算法如下：
public void selectSort(int[] arr) {
// 遍历所有的数
for (int i = 0; i < arr.length; i++) {
int minIndex = i;
// 把当前遍历的数和后面所有的数进行比较，并记录下小的数的下标
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
// 记录小的数的下标
minIndex = j;
}
}
// 如果小的数和当前遍历的下标不一致，则交换
if (i != minIndex) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
2. 堆排序
我们知道，对于任何一个数组都可以看成一颗完全二叉树。堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：
像上图的大顶堆，映射为数组，就是 [50, 45, 40, 20, 25, 35, 30, 10, 15]。可以发现个下标的元素就是最大值，将其与末尾元素交换，则末尾元素就是最大值。所以堆排序的思想可以归纳为以下两步：
根据初始数组构造堆
每次交换个和最后一个元素，然后将除最后一个元素以外的其他元素重新调整为大顶堆
重复以上两个步骤，直到没有元素可操作，就完成排序了。
我们需要把一个普通数组转换为大顶堆，调整的起始点是最后一个非叶子结点，然后从左至右，从下至上，继续调整其他非叶子结点，直到根结点为止。
/**
* 转化为大顶堆
* @param arr 待转化的数组
* @param size 待调整的区间长度
* @param index 结点下标
*/
public void maxHeap(int[] arr, int size, int index) {
// 左子结点
int leftNode = 2 * index + 1;
// 右子结点
int rightNode = 2 * index + 2;
int max = index;
// 和两个子结点分别对比，找出大的结点
if (leftNode < size && arr[leftNode] > arr[max]) {
max =&nbs
文中图片素材来源网络，如有侵权请联系删除
Java实现八种常用排序算法，你会几个？原创内容，请点击 沈阳JAVA培训
热门课程
-
沈阳java架构课程零基础培训班
询价
-
java编程速成就业班
询价
-
沈阳java零基础就业班
询价
-
java后端开发培训
询价
-
沈阳IT零基础程序员就业班
询价
