冒泡排序、堆排序、插入排序、归并排序、快速排序、选择排序、希尔排序

---

目录

一、冒泡排序

1、基本思想

2、特征总结

3、代码实现

二、堆排序

1、基本思想

2、特征总结

3、代码实现

三、插入排序

1、基本思想

2、特征总结

3、代码实现

四、选择排序

1、基本思想

2、特征总结

3、代码实现

五、希尔排序

1、基本思想

2、特征总结

3、代码实现

---

一、冒泡排序

1、基本思想

        比较相邻的两个元素，如果前者比后者大，就交换他们两个。这样每一趟排序下来都可以确定一个最大元素。（这里以升序排序为例）

2、特征总结

冒泡排序是最简单，也是最容易理解的排序。

时间复杂度：O(N^2)

空间复杂度：O(1)

稳定性：稳定

3、代码实现

（包含完整冒泡排序代码 与 n次冒泡排序代码）

public class Bubble_Sort {//完整的冒泡排序public static void bubbleSort(int[] array) {//其中：i指的是元素排序的次数 j指的是参与排序的元素个数//为什么每次要减i？// 因为每排序一次，末尾都是数组中最大的元素，为了减少时间复杂度，末尾元素不参与排序for (int i = 0; i < array.length - 1; i++) {for (int j = 0; j < array.length - i - 1; j++) {boolean flag = true;//如果后面的元素比前面的大，就交换两个元素if(array[j] > array[j+1]) {int tmp = array[j];array[j] = array[j+1];array[j+1] = tmp;flag = false;}//元素不再交换了，证明排序已经完成了 可以提前结束循环if(!flag) {break;}}}}//冒泡排序n次public static void bubbleSortIndex(int[] array, int index) {for (int i = 0; i < index; i++) {for (int j = 0; j < array.length - i - 1; j++) {//如果后面的元素比前面的大，就交换两个元素if(array[j] > array[j+1]) {int tmp = array[j];array[j] = array[j+1];array[j+1] = tmp;}}}}
}

---

二、堆排序

1、基本思想

        堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。

        需要注意的是排升序要建大堆，排降序建小堆。

2、特征总结

再次强调：升序要建大根堆，降序要建小根堆！

时间复杂度：O(N*logN)

空间复杂度：O(1)

稳定性：不稳定

3、代码实现

要进行升序排序，需要建立大根堆

public class Heap_Sort {//向下调整建立大根堆public static void siftDown(int[] array,int parent,int len) {int child = (2*parent)+1;while(child < len) {if(child+1 < len && array[child+1] > array[child]) {child++;}if(array[child] > array[parent]) {swap(array,child,parent);parent = child;child = (2*parent)+1;} else {break;}}}public static void swap(int[] array,int x,int y) {int tmp = array[x];array[x] = array[y];array[y] = tmp;}public static void creatBigheap(int[] array) {int parent = (array.length-1-1) / 2;for (int i = parent; i >= 0; i--) {siftDown(array,i, array.length);}}public static void heapSort(int[] array) {int end = array.length - 1;while(end > 0) {swap(array,0,end);siftDown(array,0,end-1);end--;}}public static void main(String[] args) {int[] arr = {1,3,5,7,9,2,4,6,8};//先建立大根堆creatBigheap(arr);System.out.print("堆排序前：");System.out.println(Arrays.toString(arr));//而后进行堆排序，使其变为升序排序System.out.print("堆排序后：");heapSort(arr);System.out.println(Arrays.toString(arr));}
}

运行结果：

---

三、插入排序

1、基本思想

        把待排序的元素按其大小逐个插入到已经排序好的有序序列中，直到所有的元素都插入完成为止，这样子就可以得到一个有序序列。

（可以理解称为我们玩斗地主时，每拿一张牌，就在原本的牌序列中找到合适的位置将新的牌插入。）

2、特征总结

时间复杂度：O(N^2)       

                   （元素有序时 —— O(N)        元素逆序时 —— O(N^2)   ）

空间复杂度：O(1)

稳定性：稳定

特点：插入排序越趋于有序，算法的时间效率越高。

3、代码实现

public class Insert_Sort {public static void insertSort(int[] array) {for (int i = 0; i < array.length; i++) {int j = i - 1;int tmp = array[i];for (; j >= 0 ; j--) {//如果比tmp大 就证明不是升序的 要往后挪动if(array[j] > tmp) {array[j+1] = array[j];} else {break;}}/*当走到这一步有两种情况：1、j<0  （0 - i-1）的元素都遍历一遍了 要把tmp放到j+1的位置填充上2、j前面的元素都比tmp小了 要把tmp放回j+1的位置*/array[j+1] = tmp;}}
}

---

四、选择排序

1、基本思想

2、特征总结

直接选择排序思想上很好理解，但是运行效率不够高。

时间复杂度：O(N^2)

空间复杂度：O(1)

稳定性：不稳定

3、代码实现

public class Select_Sort {public static void selectSort(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,i,minIndex);}}public static void swap(int[] array,int x,int y) {int tmp = array[x];array[x] = array[y];array[y] = tmp;}
}

---

五、希尔排序

1、基本思想

        希尔排序的基本思想是：先选定一个整数，把待排序序列中的所有元素分成多个组，把所有距离相同的元素放在同一组内，并对每一组内的元素进行排序。一直重复上述过程，当组与组间的距离到达1时，再排序一次，所有的元素就排好序了。

2、特征总结

希尔排序是对直接插入排序的优化。当gap > 1 时，都是预排序，当 gap == 1 时，序列已经趋近于有序了。

时间复杂度：希尔排序的时间复杂度不好计算，与gap的取值方式密切相关。因此很多书中给出的时间复杂度都不相同：

空间复杂度：O(1)

稳定性：不稳定

3、代码实现

public class Shell_Sort {public static void shellSort(int[] array) {int gap = array.length;while(gap > 1) {gap = gap / 3 + 1;//gap /= 2;   (两种都可以  前者效率更高shell(array,gap);}}public static void shell(int[] array,int gap) {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;}}
}

---

以上就是 Java：七大基于比较的排序算法——上（思想+代码实现 超详细！），希望能对你有所帮助！