排序
选择排序
- 在待排序序列中，找到最小值（大）的下标，和排好序的末尾交换，放到待排序列的开头，直到全部待排序元素排完
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;//只要比minIndex小，放进去
}
}//循环走完后，minIndex存的就是当前未排序的最小值
//将当前i的值和找到的最小值进行交换
swap(array,i,minIndex);
}
}
public static void swap(int[] array, int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
1.遍历数组长度，i从0开始
2.每次循环，都由minIndex = i 来记录最小值的下标
3.j 从i+1开始遍历，只要比记录的最小值小，就让minIndex记录。找到未排序中的最小值，进行交换
4.如果遍历完后，未排序中没有比minIndex存的值小，i的值就是最小值，i++;
- 效率低, 如果较为有序的序列，在交换时会破坏有序性
- 时间复杂度：O ( N2 )
- 空间复杂的：O ( 1 )
- 稳定性：不稳定
方法二
-
上面的方法，只是先选出最小的值，然后和i的位置交换，
-
进行优化：在遍历时选出最大值和最小值，和收尾进行交换
/**
* 选择排序---选最大值和最小值
*
* @param array
*/
public static void selectSort2(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[maxIndex]) {
maxIndex = i;
}
if (array[i] < array[minIndex]) {
minIndex = i;
}
}
//用最大值和最小值交换首位
swap(array, left, minIndex);
//把left和最小值交换
//如果left恰好就是最大值，就有可能把最大值换到minIndex的位置
if(left == maxIndex){
maxIndex = minIndex;//最大值位置不是left了，而是换到了minIndex
}
swap(array, right, maxIndex);
left++;
right--;
}
}
1.在遍历的过程中，选出最大值的下标和最小值的下标
2.将left和最小值进行交换
3.如果left恰好为最大值，left和最小值交换完成后，最大值就在原来最小值的位置上，
4.maxIndex = minIndex,修正最大值的位置
4.将right和最大值进行交换
直接插入排序和直接排序的区别
- 和插入排序不同的是，插入排序会持续对已排序的数进行比较，把合适的数放在合适的位置
- 直接选择排序就是不断找到最小的值，依次放在排好序的末尾，不干预排好的序列
2.堆排序
- 时间复杂度: O( N * log N)
- 空间复杂的：O (1)
-
升序：建大堆
-
降序：建小堆
将一组数据从小到大排序 ——> 建立大根堆
为什么不用小根堆：小根堆只能保证，根比左右小，不能保证左右孩子的大小顺序，并且要求对数组本身进行排序
- 大根堆，保证堆顶元素是最大值，最大值跟最后一个元素交换，将最大的放在最后，usedSize–；
- 向下调整：调整0下标的树，维护大根堆，最大值继续交换到最后一个有效元素的位置
- 从后往前，从大到小依次排列，保证在原来数组本身进行排序
/**
* 堆排序
* 时间复杂度: N*logN
* 空间复杂的：o(1)
*
* @param array
*/
public static void heapSort(int[] array) {
createBigHeap(array);//创建大根堆
int end = array.length-1;
while (end>0){
swap(array,0,end);//堆顶元素和末尾互换
shiftDown(array,0,end);//维护大根堆
end--;
}
}
/**
* 创建大根堆
*
* @param array
*/
public static void createBigHeap(int[] array) {
//最后一个结点的下标 = array.length - 1
//它的父亲结点的下标就为array.length - 1 - 1) / 2
for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
shiftDown(array, parent, array.length);
}
}
/**
* 向下调整
*
* @param array
* @param parent
* @param len
*///向下调整，每棵树从父结点向下走
public static void shiftDown(int[] array, int parent, int len) {
int child = parent * 2 + 1;
while (child < len) {
//child < len:最起码要有一个左孩子
if (child + 1 < len && array[child] < array[child + 1]) {
child++;
}//child + 1<len:保证一定有右孩子的情况下，和右孩子比较
//拿到子节点的最大值
if (array[child] > array[parent]) {
swap(array, child, parent);
parent = child;//交换完成后，让parent结点等于等于当前child结点
child = 2 * parent + 1;
//重新求子节点的位置，再次进入循环交换
} else {
break;
//比父结点小，结束循环
}
}
}
- 时间复杂度: O( N * log 2N)
- 空间复杂的：O (1)
- 稳定性：不稳定
点击移步博客主页，欢迎光临~
