1. 冒泡排序
排序原理：数组元素两两比较，交换位置，大元素往后放，那么经过一轮比较后，最大的元素，就会出现在最大素引处。
/**
* @description 冒泡排序
* @author: PeiChen
* @version 1.0
*/
public class BubbleSort {
public static void main(String[] args) {
int[] arr = {1, 24, 16, 8, 36, 5};
BubbleSort.bubbleSort(arr);
System.out.println(Arrays.toString(arr));
}
/**
* 排序原理：数组元素两两比较，交换位置，大元素往后放，那么经过一轮比较后，最大的元素，就会出现在最大素引处。
* @param array 待排序数组
*/
private static void bubbleSort(int[] array) {
for (int i = 0; i < array.length - 1; 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;
}
}
}
}
}
排序结果：
[1, 5, 8, 16, 24, 36]2. 选择排序
排序原理：从0索引处开始，依次和后面的元素进行比较，小的元素往前放,经过一轮比较后，最小的元素就出现在了最小索引处。
/**
* @description 选择排序
* @author: PeiChen
* @version 1.0
*/
public class SelectSort {
public static void main(String[] args) {
int[] arr = {1, 24, 16, 8, 36, 5};
SelectSort.selectSort(arr);
System.out.println(Arrays.toString(arr));
}
/**
* 排序原理：从0索引处开始，依次和后面的元素进行比较，小的元素往前放,经过一轮比较后，最小的元素就出现在了最小索引处。
* @param array 待排序数组
*/
private static void selectSort(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
for (int j = i + 1; j < array.length; j++) {
if (array[i] > array[j]) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
}
}
排序结果：
[1, 5, 8, 16, 24, 36]3. 插入排序
直接插入排序：从 1 索引处开始，将后面的元素依次插入到之前的有序列表中使之仍保持有序。
/**
* @description 直接插入排序
* @author: PeiChen
* @version 1.0
*/
public class InsertSort {
public static void main(String[] args) {
int[] arr = {1, 24, 16, 8, 36, 5};
insertSort(arr);
System.out.println(Arrays.toString(arr));
}
/**
* 直接插入排序：从 1 索引处开始，将后面的元素依次插入到之前的有序列表中使之仍保持有序。
* @param array 待排序数组
*/
private static void insertSort(int[] array) {
//控制循环的次数
for (int i = 1; i < array.length; i++) {
int j = i;
//升序排列直接插入，否则交换元素插入
while (j > 0 && array[j] < array[j - 1]) {
int temp = array[j];
array[j] = array[j - 1];
array[j - 1] = temp;
j--;
}
}
}
}排序结果：
[1, 5, 8, 16, 24, 36]4. 希尔排序
希尔排序：它是对直接插入排序的一个优化，核心的思想就是合理的选取增量，经过一轮排序后,就会让序列大致有序，然后再不断的缩小增量，进行插入排序，直到增量为 1 ，即整个排序结束。
/**
* @description 希尔排序
* @author: PeiChen
* @version 1.0
*/
public class ShellSort {
public static void main(String[] args) {
int[] arr = {1, 24, 16, 8, 36, 5, 21, -2, 52};
shellSort(arr);
System.out.println(Arrays.toString(arr));
}
/**
* 希尔排序：它是对直接插入排序的一个优化，核心的思想就是合理的选取增量，经过一轮排序后,就会让序列大致有序，
* 然后再不断的缩小增量，进行插入排序，直到增量为 1 ，即整个排序结束。
* @param array 待排序数组
*/
private static void shellSort(int[] array) {
//根据克努特序列选取我们第一次的增量
int interval = 1;
while (interval <= array.length / 3) {
interval = interval * 3 + 1;
}
//控制增量步长
for (int step = interval; step > 0; step = (step - 1) / 3) {
//控制循环次数
for (int i = step; i < array.length; i++) {
//控制插入元素
for (int j = i; j >= step; j -= step) {
if (array[j] < array[j - step]) {
int temp = array[j];
array[j] = array[j - step];
array[j - step] = temp;
}
}
}
}
}
}排序结果：
[-2, 1, 5, 8, 16, 21, 24, 36, 52]5. 快速排序
分治法：比大小，再分区
- 从数组中取出一个数,作为基准数。
- 分区：将比这个数大或等于的数全放到他的右边，小于它的数全放到它的左边。
- 再对左右区间重复第二步，直到各区间只有一个数。
/**
* @description 快速排序
* @author: PeiChen
* @version 1.0
*/
public class QuickSort {
public static void main(String[] args) {
int[] arr = {1, 24, 16, 8, 36, 5, 21, -2, 52};
quickSort(arr,0,arr.length - 1);
System.out.println(Arrays.toString(arr));
}
private static void quickSort(int[] array, int start, int end) {
//找出分开左右分区的索引位置，然后分别对左右两区进行递归排序
if (start < end) {
int index = partition(array, start, end);
quickSort(array,start,index - 1);
quickSort(array,index + 1,end);
}
}
/**
* 1.将基准数挖出形成第一个坑
* 2.由后向前找比他小的数,找到后挖出此数填到前一个坑中
* 3.由前向后找比他大或等于的数,找到后也挖出此数填到前一个坑中
* 4.再重复执行2,3两步骤。
* @param array 待分区数组
* @param start 起始位置
* @param end 终止位置
* @return 分区的索引
*/
private static int partition(int[] array, int start, int end) {
int i = start;
int j = end;
//将基准数挖出形成第一个坑
int baseVal = array[i];
while (i < j) {
//由后向前找比较小的数，找到后挖出此数填到一个坑中
while (i < j && array[j] >= baseVal) {
j--;
}
if (i < j) {
array[i] = array[j];
i++;
}
//由前向后找比较大或等于的数，找到后也挖出此数填到前一个坑中
while (i < j && array[i] < baseVal) {
i++;
}
if (i < j) {
array[j] = array[i];
j--;
}
//把基准数填到最后一个坑中
array[i] = baseVal;
}
return i;
}
}排序结果：
[-2, 1, 5, 8, 16, 21, 24, 36, 52]6. 归并排序
归并排序( Merge Sort)就是利用归并的思想实现排序的方法。它的原理是假设初始序列有N个记录，则可以看成是N个有序的子序列，每个子序列的长度为 1 ，然后两两归并得到N/2个长度为2或1的有序子序列，再两两归并... 如此重复直至得到一个长度为N的有序序列为止，这种排序方法称为2路归并排序。
/**
* @description 归并排序
* @author: PeiChen
* @version 1.0
*/
public class MergeSort {
public static void main(String[] args) {
int[] arr = {1, 24, 16, 8, 36, 5, 21, -2, 52};
split(arr,0,arr.length - 1);
System.out.println(Arrays.toString(arr));
}
/**
* 拆分数组
* @param arr 原始数组
* @param startIndex 起始索引
* @param endIndex 结束索引
*/
private static void split(int[] arr, int startIndex, int endIndex) {
//寻找中间索引
int centerIndex = (startIndex + endIndex) / 2;
if (startIndex < endIndex) {
split(arr,startIndex,centerIndex);
split(arr,centerIndex + 1,endIndex);
merge(arr,startIndex,centerIndex,endIndex);
}
}
/**
* 归并数组
* @param arr 原始数组
* @param startIndex 起始索引
* @param centerIndex 中间索引
* @param endIndex 结束索引
*/
private static void merge(int[] arr, int startIndex, int centerIndex, int endIndex) {
int[] tempArr = new int[endIndex - startIndex + 1];
//定义左边数组的起始索引
int i = startIndex;
//定义右边数组的起始索引
int j = centerIndex + 1;
//临时数组的起始索引
int index = 0;
//比较两个数组中的元素大小，然后往临时数组里添加
while (i <= centerIndex && j <= endIndex) {
if (arr[i] <= arr[j]) {
tempArr[index] = arr[i];
i++;
} else {
tempArr[index] = arr[j];
j++;
}
index++;
}
//处理剩余元素
while (i <= centerIndex) {
tempArr[index] = arr[i];
i++;
index++;
}
while (j <= endIndex) {
tempArr[index] = arr[j];
j++;
index++;
}
//将临时数组的元素取到原始数组中
for (int k = 0; k < tempArr.length; k++) {
arr[startIndex + k] = tempArr[k];
}
}
}排序结果：
[-2, 1, 5, 8, 16, 21, 24, 36, 52]7. 基数排序
基数排序不同于之前所介绍的各类排序，前边介绍到的排序方法或多或少的是通过使用比较和移动记录来实现排序。而基数排序的实现不需要进行对关键字的比较，只需要对关键字进行"分配"与"收集"两种操作即可完成。
/**
* @description 基数排序(桶排序)(此案例只适用于非负数，负数再加一个判断即可)
* @author: PeiChen
* @version 1.0
*/
public class BaseSort {
public static void main(String[] args) {
int[] arr = {1, 24, 16, 8, 36, 28, 5, 21, 2, 52, 666, 127, 520, 68};
baseSort(arr);
System.out.println(Arrays.toString(arr));
}
/**
* 基数排序：先分配再收集
* @param arr 待排序数组
*/
private static void baseSort(int[] arr) {
//定义二维数组，放10个桶
int[][] tempArr = new int[10][arr.length];
//定义统计数组
int[] counts = new int[10];
//计算最大数的位数
int maxLength = getMaxLength(arr);
//循环次数
for (int i = 0, k = 1; i < maxLength; i++, k*= 10) {
//分配
for (int value : arr) {
//获取每位上的数字
int everyNum = value / k % 10;
//放到对应的桶内，并且对每个桶中的元素计数
tempArr[everyNum][counts[everyNum]++] = value;
}
//收集
int index = 0;
for (int m = 0; m < counts.length; m++) {
if (counts[m] != 0) {
for (int n = 0; n < counts[m]; n++) {
//从桶中取出元素放入原数组
arr[index++] = tempArr[m][n];
}
//清空上一次统计的个数
counts[m] = 0;
}
}
}
}
private static int getMaxLength(int[] arr) {
int max = arr[0];
for (int num : arr) {
if (num > max) {
max = num;
}
}
return String.valueOf(max).length();
}
}排序结果：
[1, 2, 5, 8, 16, 21, 24, 28, 36, 52, 68, 127, 520, 666]8. 堆排序
堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序。
堆排序的基本思想：
- 将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。
- 将其与末尾元素进行交换，此时末尾就为最大值。
- 然后将剩余 n-1 个元素重新构造成一个堆，这样会得到 n 个元素的次小值。
- 如此反复执行，便能得到一个有序序列了。
/**
* @description 堆排序
* @author: PeiChen
* @version 1.0
*/
public class HeapSort {
public static void main(String[] args) {
int[] arr = {1, 24, 16, 8, 36, 28, 5, 21, 2, 52, 666, 127, 520, 68};
//开始调整的位置
int startIndex = (arr.length - 1) / 2;
//循环调整大顶堆
for (int i = startIndex; i >= 0; i--) {
toBigHeap(arr,arr.length,i);
}
//循环把根元素与最后一个元素进行交换
for (int i = arr.length - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
//调整完之后继续把剩余元素调整为大顶堆
toBigHeap(arr,i,0);
}
System.out.println(Arrays.toString(arr));
}
/**
* 把一个数组转换成大顶堆
* @param arr 原始数组
* @param size 调整的元素个数
* @param index 开始调整的位置
*/
private static void toBigHeap(int[] arr, int size, int index) {
//获取左右子节点的索引
int leftNodeIndex = index * 2 + 1;
int rightNodeIndex = index * 2 + 2;
//查找最大节点所对应的索引
int maxIndex = index;
if (leftNodeIndex < size && arr[leftNodeIndex] > arr[maxIndex]) {
maxIndex = leftNodeIndex;
}
if (rightNodeIndex < size && arr[rightNodeIndex] > arr[maxIndex]) {
maxIndex = rightNodeIndex;
}
//如果最大元素不是当前元素，则需调换位置
if (maxIndex != index) {
int temp = arr[maxIndex];
arr[maxIndex] = arr[index];
arr[index] = temp;
//交换完位置以后很有可能会破坏原先大顶堆结构，所以还需重新调换
toBigHeap(arr,size,maxIndex);
}
}
}排序结果：
[1, 2, 5, 8, 16, 21, 24, 28, 36, 52, 68, 127, 520, 666]
