堆排序和快排序笔记
堆排序
一些相关的概念 堆是一棵顺序存储的完全二叉树。 大根堆：每个结点的值都大于或等于子结点的值，这样的堆称为大根堆。 小根堆：每个结点的值都小于或等于子结点的值，这样的堆称为小根堆。 建立一个大根堆的时间复杂度为O(N) 二叉树在数组中的表示：对于索引为K的父节点，其左孩子为（2K+1） 右孩子为（ 2K+2）。一个节点的父节点索引为(K-1)/2。 堆排序的思想 将待排序的n个元素构造成一个大顶堆(小顶堆也可以，下面以大顶堆为例)。此时，这个序列的最大值就是大顶堆的根结点；然后，将大顶堆的根结点与堆数组中的最后一个元素进行交换，交换后，大顶堆的根结点存放的就是堆数组中的最后一个元素，大顶堆的根结点中存储的原始的最大值被移走啦；接着，将剩下的n-1个元素重新调整后，构造成一个新的大顶堆，重复上面的步骤，被移动的元素就构成了一个有序的数据。 整个步骤有两个关键操作 1.建立大根堆。从右至左，从下往上进行调整
原始位置：
数据原始顺序
调整一次过后
调整一次过后
2.将根节点与最后一个元素交换，使末尾元素最大，然后重新构建大根堆。 将最后一个元素与根节点互换
在这里插入图片描述
重新调整
在这里插入图片描述
程序代码
import java.util.Arrays;
public class HeapSort{
public static void heapSort(int[] arr){
if(arr.length < 2 || arr == null){
return;
}
for(int index = 0; index < arr.length; index++){
heapInsert(arr,index);
}
int heapSize = arr.length;
swap(arr, 0, --heapSize);
while(heapSize > 0){
heapify(arr, 0, heapSize);
swap(arr, 0, --heapSize);
}
}
public static void swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void heapInsert(int[] arr, int index){
while(arr[index] > arr[(index - 1) / 2]){
swap(arr, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
public static void heapify(int[] arr, int index, int heapSize){
int left = 2 * index + 1;
while(left < heapSize){
int max = (left + 1 < heapSize ) && (arr[left + 1] > arr[left])
? left + 1: left;
max = arr[max] > arr[index] ? max : index;
if(index == max){
break;
}
swap(arr, max, index);
index = max;
left = 2 * index + 1;
}
}
//for test
public static void comparator(int[] arr){
Arrays.sort(arr);
}
public static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
}
return arr;
}
public static int[] copyArray(int[] arr) {
if (arr == null) {
return null;
}
int[] res = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
res[i] = arr[i];
}
return res;
}
// for test
public static boolean isEqual(int[] arr1, int[] arr2) {
if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
return false;
}
if (arr1 == null && arr2 == null) {
return true;
}
if (arr1.length != arr2.length) {
return false;
}
for (int i = 0; i < arr1.length; i++) {
if (arr1[i] != arr2[i]) {
return false;
}
}
return true;
}
// for test
public static void printArray(int[] arr) {
if (arr == null) {
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
int testTimes = 100;
int maxSize = 10;
int maxValue = 100;
boolean succeed = true;
for( int i = 0; i < testTimes; i++){
int[] arr1 = generateRandomArray(maxSize,maxValue);
int[] arr2 = copyArray(arr1);
heapSort(arr1);
comparator(arr2);
if (!isEqual(arr1, arr2)) {
succeed = false;
break;
}
System.out.println(succeed ? "Nice!" : "Fucking fucked!");
int[] arr = generateRandomArray(maxSize, maxValue);
heapSort(arr);
printArray(arr);
}
}
}快排
荷兰国旗问题 给定一个整数数组，给定一个值K，这个值在原数组中一定存在，要求把数组中小于K的元素放到数组的左边，大于K的元素放到数组的右边，等于K的元素放到数组的中间，最终返回一个整数数组，其中只有两个值，分别是等于K的数组部分的左右两个下标值。
例如，给定数组：[2, 3, 1, 9, 7, 6, 1, 4, 5]，给定一个值4，那么经过处理原数组可能得一种情况是：[2, 3, 1, 1, 4, 9, 7, 6, 5]，需要注意的是，小于4的部分不需要有序，大于4的部分也不需要有序，返回等于4部分的左右两个下标，即[4, 4]
在这里插入图片描述
- less 用于记录小于 4 的区域的右下标，初始为-1，代表不存在
- more 用于记录大于 4 区域的左下标，初始为9，代表不存在
- L 用于正在遍历的元素的下标，初始值为0
- 从 arr[L] 即 arr[0] 开始遍历数组
- 如果 arr[L] > 4, 交换 arr[++ less] 和 arr[L++] 的值
- 如果 arr[L] < 4, 交换 arr[–more] 和 arr[L] 的值
- 如果 arr[L] = 4, 不交换，L++，直接遍历下一个值
- 当 L >= more，退出循环。
public class heland {
public static int[] partition(int[] arr, int l, int r, int p) {
int less = l - 1;
int more = r + 1;
while (l < more) {
if (arr[l] < p) {
swap(arr, ++less, l++);
} else if (arr[l] > p) {
swap(arr, --more, l);
} else {
l++;
}
}
return new int[] { less + 1, more - 1 };
}
// for test
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
// for test
public static int[] generateArray() {
int[] arr = new int[15];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) (Math.random() * 20);
}
return arr;
}
// for test
public static void printArray(int[] arr) {
if (arr == null) {
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[] test = generateArray();
printArray(test);
int[] res = partition(test, 0, test.length - 1, 8);
printArray(test);
System.out.println(res[0]);
System.out.println(res[1]);
}
}随机快速排序 经典快速排序总是指定数组或者某部分的最后一个元素作为基准值，随机快速排序指定数组或者某一部分中的随机值作为基准值。
在这里插入图片描述
/**
* 快速排序，使得整数数组 arr 有序
*/
public static void quickSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
quickSort(arr, 0, arr.length - 1);
}
/**
* 快速排序，使得整数数组 arr 的 [L, R] 部分有序
*/
public static void quickSort(int[] arr, int L, int R) {
if(L < R) {
// 把数组中随机的一个元素与最后一个元素交换，这样以最后一个元素作为基准值实际上就是以数组中随机的一个元素作为基准值
swap(arr, new Random().nextInt(R - L + 1) + L, R);
int[] p = partition(arr, L, R);
quickSort(arr, L, p[0] - 1);
quickSort(arr, p[1] + 1, R);
}
}
/**
* 分区的过程，整数数组 arr 的[L, R]部分上，使得：
* 大于 arr[R] 的元素位于[L, R]部分的右边，但这部分数据不一定有序
* 小于 arr[R] 的元素位于[L, R]部分的左边，但这部分数据不一定有序
* 等于 arr[R] 的元素位于[L, R]部分的中间
* 返回等于部分的第一个元素的下标和最后一个下标组成的整数数组
*/
public static int[] partition(int[] arr, int L, int R) {
int basic = arr[R];
int less = L - 1;
int more = R + 1;
while(L < more) {
if(arr[L] < basic) {
swap(arr, ++less, L++);
} else if (arr[L] > basic) {
swap(arr, --more, L);
} else {
L++;
}
}
return new int[] { less + 1, more - 1 };
}
/*
* 交换数组 arr 中下标为 i 和下标为 j 位置的元素
*/
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020-09-28，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
