文章目录
- 排序的概念
- 直接插入排序
- 希尔排序( 缩小增量排序)
- 选择排序
- 堆排序
- 冒泡排序
在计算机科学中，排序算法是一类重要的算法，它们用于将一组元素按照一定的顺序进行排列。在Java编程中，我们经常需要对数组或集合进行排序操作。本文将介绍Java中七种常见的排序算法，并附带详细的分析过程和代码实现。
排序的概念
排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
直接插入排序
思路：
- 定义下标 i 和 j 以及临时变量tmp，并把下标 i 的元素存放在tmp中
- j 从 i-1 的位置，开始向前遍历，遇到比 tmp大的元素，就把此时 j 下标的元素往后移一位，直到 j 下标小于0停止。
- j 下标元素小于tmp，则把tmp元素插入该j下标的下一个位置。
代码实现
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;
}
}
总结
- 元素集合越接近有序，直接插入排序算法的时间效率越高
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)，它是一种稳定的排序算法
- 稳定性：稳定
希尔排序( 缩小增量排序)
希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成多个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。
思路：
- 定义gap = 数组长度\2。
- 把待排序列分为gap个组，每个组的第一个元素和最后一个元素进行比较交换。
- 重复上述操作
- 当gap为1时，进行插入排序。
代码实现
public static void shellSort(int[] array) {
int gap = array.length;//n
while (gap > 1) {
gap = gap/3 + 1;
shell(array,gap);
}
}
private static void shell(int[] array,int gap) {
//i++ 交替进行插入排序
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;
}
}
时间复杂度： O(N^1.3);
空间复杂度： O(1);
稳定性： 不稳定。
希尔排序的特性总结：
- 希尔排序是对直接插入排序的优化。
- 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了
- 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定。
选择排序
思路： 每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。
实现：
- 定义 i 和 j 以及临时下标minIndex,minIndex记录 i 的下标。
- j 从 i 下一个位置开始往后遍历，遇到小于array[minIndex]时更新min，min指向每次遍历的最小值下标，直到遍历完一次数组。
- 一次遍历完后array[i]和minIndex下标进行交换。
代码实现
private static void swap(int[] array,int i,int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
public static void selectSort1(int[] array) {
for (int i = 0; i < array.length; i++) {
int minIndex = i;
for (int j = i+1; j < array.length; j++) {
if(array[j] < array[minIndex]) {
minIndex = j;
}
}
swap(array,minIndex,i);
}
}
总结：
时间复杂度： O(N^2);
空间复杂度: O(1);
稳定性： 不稳定；
堆排序
注意：排升序需要建大根堆，排降序建小根堆。此文章默认举例排升序。
思路：
- 首先得建立一个大根堆。
- 把根节点与最后一个节点交换，每一次交换，最后一个节点向前走一步。
- 进行堆向下调整。
代码实现：
private static void createBigHeap(int[] array) {
for (int parent = (array.length-1-1) / 2; parent >= 0; parent--) {
siftDown(parent,array,array.length);
}
}
private static void siftDown(int parent,int[] array,int end) {
int child = 2*parent+1;
while (child < end) {
if(child + 1 < end && array[child] < array[child+1]) {
child++;
}
//child下标 就是左右孩子最大值的下标
if(array[child] > array[parent]) {
swap(array,child,parent);
parent = child;
child = 2*parent+1;
}else {
break;
}
}
}
public static void heapSort(int[] array) {
createBigHeap(array);
int end = array.length-1;
while (end >= 0) {
swap(array,0,end);
siftDown(0,array,end);
end--;
}
}
冒泡排序
思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
- 定义i遍历数组，控制趟数，总体趟数比数组长度少1；
- 每趟让一个较大值移动到尾部。
- 定义j每次从0下标进行两两比较交换。
public static void bubbleSort(int[] array) {
for (int i = 0; i < array.length-1; i++) {
boolean flg = false;
for (int j = 0; j < array.length-1-i; j++) {
if(array[j] > array[j+1]) {
swap(array,j,j+1);
flg = true;
}
}
if(!flg) {
break;
}
}
总结
- 冒泡排序是一种非常容易理解的排序
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：稳定
本文介绍了Java中七大常见的排序算法，包括冒泡排序、选择排序、插入排序、希尔排序和堆排序。每种排序算法的原理、实现方法和代码实现都有详细的解释和示例。通过学习和理解这些排序算法，我们可以更好地应用它们来解决实际问题，并提高程序的效率和性能。
