当前位置：首页 > news >正文

选择排序与堆排序

news 来源：原创 2024/7/27 11:23:59

博主主页: 码农派大星.

数据结构专栏:Java数据结构

数据库专栏:MySQL数据库

关注博主带你了解更多数据结构知识

1.选择排序

第一种方法:直接定义一个 i下标 和 j下标(j=i+1) ,再定义minIdex下标让 minIdex == i, 开始遍历数组,过程中如果j下标的值大于minIdex下标的值就交换,然后i++,j++.

 private static void swap(int[] arrary,int i,int j){int tmp = arrary[i];arrary[i] = arrary[j];arrary[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);}
return arrary;}

第二种方法:

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

在元素集合array[i]到array[n-1]中选择关键码最大(小)的数据元素若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素.

选择排序效果图

 private static void swap(int[] arrary,int i,int j){int tmp = arrary[i];arrary[i] = arrary[j];arrary[j] = tmp;}public static void selectSort2(int[] array){int left = 0;int right = array.length -1;while (left < right){int mindIndex = left;int maxIndex = left;for (int i = left+1; i <= right; i++) {if (array[i] < array[mindIndex]) {mindIndex = i;}if (array[i] > array[maxIndex]) {maxIndex = i;}}swap(array,mindIndex,left);if (maxIndex == left) {maxIndex = mindIndex;}swap(array,maxIndex,right);left++;right--;}
return arrary;}

总结:

1. 直接选择排序思考非常好理解，但是效率不是很好。

2. 时间复杂度：O( $n^{2}$ )

3. 空间复杂度：O(1)

4. 稳定性：不稳定

2.堆排序

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

 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--;}}

总结:

1. 堆排序使用堆来选数，效率就高了很多。

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

3. 空间复杂度：O(1)

4. 稳定性：不稳定