百度seo公司整站优化_外贸人才网是b2b还是b2c_优化人员配置_设计一个公司网站多少钱

目录

直接选择排序

 堆排序

---

基本思想：

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

直接选择排序

思路1：

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

 

    //选择排序/*** 时间复杂度：O(N^2) 和数据 是否有序无关* 空间复杂度：O(1)* 稳定性：不稳定* @param array*/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);}}private static void swap(int[] array, int i, int minIndex) {int tmp = array[i];array[i] = array[minIndex];array[minIndex] = tmp;}

 思路2：

1. 定义left和right分别去找最大值和最小值对应的下标
2. 找到后进行交换
3. 一开始最大值和最小值下标均为left，为0

 

private static void swap(int[] array, int i, int minIndex) {int tmp = array[i];array[i] = array[minIndex];array[minIndex] = tmp;
}public static void selectSort1(int[] array){int left = 0;int right = array.length-1;while(left < right){int minIndex = left;int maxIndex = left;for (int i = left+1; i <= right; i++) {if(array[i] < array[minIndex]){minIndex = i;}if(array[i] > array[maxIndex]){maxIndex = i;}}swap(array, left, minIndex);//确保最大值的位置，最大值正好是 left 下标//此时把最大值换到了minIndex下标if(maxIndex == 0){maxIndex = minIndex;}swap(array, right, maxIndex);left++;right--;}
}

 堆排序

这里我们选择大根堆进行输出，首先通过向下调整来进行创建大根堆。

public static void createHeap(int[] array){for (int parent = (array.length-1-1)/2; parent >= 0; parent--) {siftDown(array,parent,array.length);//向下调整，创建大根堆}
}public static void siftDown(int[] array, int parent, int length) {int child = 2*parent+1;while(child < length){if(child + 1 < length && array[child] < array[child +1]){child++;}if(array[child] > array[parent]){swap(array, child, parent);parent = child;child = 2*parent+1;}else{break;}}

 然后再对大根堆进行输出，完整代码如下：

public static void heapSort(int[] array){createHeap(array);int end  = array.length-1;while(end > 0){swap(array, 0 ,end);siftDown(array, 0,end);end--;}
}public static void createHeap(int[] array){for (int parent = (array.length-1-1)/2; parent >= 0; parent--) {siftDown(array,parent,array.length);//向下调整，创建大根堆}
}public static void siftDown(int[] array, int parent, int length) {int child = 2*parent+1;while(child < length){if(child + 1 < length && array[child] < array[child +1]){child++;}if(array[child] > array[parent]){swap(array, child, parent);parent = child;child = 2*parent+1;}else{break;}}
}