文章内容均来自bilibili黑马视频，本文仅记录于总结。
- 排序算法总结(二分,冒泡,选择,插入,希尔,快排)
- 1. 二分查找
- 1.1 实现步骤
- 1.2 代码实现
- 1.3 优化
- 1.4 面试题
- 2. 冒泡排序
- 2.1 v1版本
- 2.1 v2 版本 减少比较次数
- 2.1 v3 版本 减少不必要的冒泡
- 2.1 最终版本 减少比较次数PLUS
- 3. 选择排序
- 3.1 冒泡VS 选择
- 4. 插入排序
- 4.1 插入VS 选择
- 5. 快速排序
- 5.1 单边循环 lomuto 洛穆托分区方案
- 5.2 双边循环 并不完全等价于hoare霍尔分区方案
- 首先保证数组已经是有序的
- 定义左边界L，右边界R,确定搜索范围，循环执行二分查找
- 获取中间索引M=(L+R)/2
- 如果array[m]=T （T为要查找的值）直接返回中间索引
- 如果array[m]>T 表示T在 (l,m-1)之间，设置r=m-1
- 如果array[m]
- 当L>R，表示没有找到，结束循环
public static void main(String[] args) {
int[] array = {1, 2, 4, 8, 24, 38, 47, 56, 63, 74, 86, 99};
int target = 86;
int i = binarySearch(array, target);
System.out.println(i);
}
public static int binarySearch(int[] array,int target) {
int l = 0, r = array.length - 1, m;
while (l <= r) {
m = (l + r) / 2;
if (array[m] == target) {
return m;
} else if (array[m] > target) {
r = m - 1;
}else{
l = m + 1;
}
}
return -1;
}
1.3 优化
上面的代码中有一个小地方需要考虑，当左边界和右边界的值都比较大时，计算中间值时会发生整数溢出，导致符号位改变。
这句话什么意思呢
假设我们一开始设置 l=0, r=Integer.MAX_VALUE - 1
一开始算中间值(l+r)/2没得问题，但是如果我们要搜索的值在临近右块区域，则我们要将左边界l设置为m+1,我们都知道整数的最大值大约在20亿左右，中间值就是十亿，十亿+二十亿将导致整数溢出，修改整数的符号位。
int l =0;
int r = Integer.MAX_VALUE - 1;
int m = (l + r) / 2;
System.out.println(m);
l = m + 1;
m = (l + r) / 2;
System.out.println(m);
解决办法：
变换求中间值的公式
既(l+r) /2 => l-l/2+ r/2 => l+(r-l)/2
int l =0;
int r = Integer.MAX_VALUE - 1;
int m =l+ (r-l) / 2;
System.out.println(m);
l = m + 1;
m =l+ (r-l) / 2;
System.out.println(m);
其实还有另一种变换方式，当r+l超过整数范围，修改符号位，那么我们将符号位修正，也就是右移一位不是又得到正确结果了吗
那么就是(l+r)/2 变换公式 (l+r)>>>1 即可
在拥有128个元素的数组中二分查找一个数，需要比较的次数最多不超过多少次？
答案：7次
因为2的7次方=128
那如果数比较大怎么计算呢？ 假设40亿元素数组查找一个数
可以使用对数 以2为低的log（40亿）
private static void bubbing(int[] array) {
for (int i = 0; i < array.length-1; i++) {
for (int j = 0; j < array.length-1; j++) {
if (array[j] > array[j+1]) {
swap(array, j, j + 1);
}
}
}
}
public static void swap(int[] a, int i, int j) {
int m = a[i];
a[i] = a[j];
a[j] = m;
}
2.1 v2 版本 减少比较次数
一轮冒泡之后，其实最大值已经移动到了最后一位，所以就不用跟最后一位在比较了，所以每次循环的次数需要是个变量。既：
private static void bubbing(int[] array) {
for (int i = 0; i < array.length-1; i++) {
for (int j = 0; j < array.length-1-i; j++) {
if (array[j] > array[j+1]) {
swap(array, j, j + 1);
}
}
}
}
public static void swap(int[] a, int i, int j) {
int m = a[i];
a[i] = a[j];
a[j] = m;
}
2.1 v3 版本 减少不必要的冒泡
刚才的v2版本减少的是内存循环的比较，但是可能会出现一中情况，比如说一个数组9个元素我们需要循环8次，去进行冒泡，可能第4次的时候，已经完成了排序，但是程序还在执行，那么如何判断数组已经有序了呢？ 既在一轮冒泡中没有发生交换，就意味着数组已经有序。
private static void bubbing(int[] array) {
boolean swapped = false; //在一轮冒泡中是否发生了比较
for (int i = 0; i < array.length-1; i++) {
for (int j = 0; j < array.length-1-i; j++) {
if (array[j] > array[j+1]) {
swap(array, j, j + 1);
swapped = true;
}
}
if (true) {
break;
}
}
}
public static void swap(int[] a, int i, int j) {
int m = a[i];
a[i] = a[j];
a[j] = m;
}
2.1 最终版本 减少比较次数PLUS
假设一个数组中里面的元素其实有序度还是有的，比如一个 1,7,3,5,2,8,9 这样的一个数组，其实后置位已经排列好了，我们主要是向对8前面的元素进行比较，但是基于之前版本的冒泡却要每次都要比较。那么如何做到呢？我们可以拿到最后交换的元素索引作为下一次冒泡的比较次数，既：
private static void bubbing(int[] array) {
int n = array.length - 1;
while (true) {
int last_swap_index = 0;
for (int j = 0; j < n; j++) {
if (array[j] > array[j+1]) {
swap(array, j, j + 1);
last_swap_index = j;
}
}
n = last_swap_index;
if (n == 0) {
break;
}
}
}
public static void swap(int[] a, int i, int j) {
int m = a[i];
a[i] = a[j];
a[j] = m;
}
3. 选择排序
选择排序的精髓在于将一个数组分为两个区域分别是已排序区域和未排序区域，然后遍历未排序区域移动到已排序区域，既每次遍历选择，都选出来最小（或最大）的值放在已排序区域。实现如下：
private static void selectionSort(int[] array) {
for (int i = 0; i < array.length-1; i++) {
//i 代表的是什么意思？ 表示每轮选择出的最小元素要交换的已排序区域的索引
int s = i; //s 表示最小元素的索引
for (int j = s+1; j < array.length; j++) {
if (array[s] > array[j]) {
s = j;
}
}
if (s != i) {
swap(array, i, s);
}
}
}
public static void swap(int[] a, int i, int j) {
int m = a[i];
a[i] = a[j];
a[j] = m;
}
其中外层循环表示 要选择的次数，内存循环表示比较的次数
3.1 冒泡VS 选择- 二者平均时间复杂度都是O(n的2次方)
- 选择排序一般要快于冒泡，因为其交换次数少
- 如果集合有序度高，冒泡优于选择
- 冒泡属于稳定排序算法，而选择属于不稳定排序
解释：
为什么说一般选择要快于冒泡呢，因为选择排序，每一轮选择最小的元素只发生了一次交换，但是冒泡就不一样了，一轮中都得交换好多次。
那么为什么又说有序度高时，冒泡优于选择呢，假如给定了一个有序的数组
冒泡只需要经过一次排序，就可以判断出来数组是有序的直接break
但是选择排序算法决定了它不清楚什么时候数组是有序的，只能一轮轮的选完。
那么什么是稳定排序算法呢？
既多轮排序之后，相同的元素位置不发生改变，而不稳定排序则可能相同的元素位置发生了改变，如下图所示：
分别使用了选择排序和冒泡排序
第一次排序根据花色，第二轮根据数值
会发现不稳定排序中，第一次排序 黑桃2在红桃2之前
但是在第二次排序之后红桃2在黑桃2之前，这就是不稳定排序。
插入排序于选择排序有一点像，都是将一个数组划分为两个区域，已排序区域和未排序区域，遍历数组的同时，扩大已排序区域，将扩大的那个元素拿出来，称为一个待插入元素，和前面的已排序区域元素进行比较，找到它应该插入的区域（既比已排序区域的某个元素大的时候）。
public static void main(String[] args) {
int[] array = {1, 45, 87, 47, 243, 99, 67, 52, 81};
insertSort(array);
System.out.println(Arrays.toString(array));
}
private static void insertSort(int[] array) {
//i 代表待插入元素的索引
for (int i = 1; i < array.length; i++) {
int n = array[i];
int j =i-1; //j 表示已排序区域的右边界元素索引
while (j >= 0) {
if (n < array[j]) { //表示已排序区域的右边界元素需要朝后移动一位
array[j + 1] = array[j];
} else{ //表示n就该插入这个位置
break;
}
j--;
}
array[j + 1] = n;
}
}
4.1 插入VS 选择
- 二者平均时间复杂度都是O(n的二次方)
- 大部分情况下，插入都略优于选择
- 有序集合插入的时间复杂度为O(n)
- 插入属于稳定排序算法，而选择属于不稳定排序
特点：
一 . 每一轮排序选择一个基准点（pivot）进行分区
1. 让小于基准点的元素进入一个分区，大于基准点的元素进入另一个分区
2. 当分区完成时，基准点元素的位置就是其最终位置
二. 在子分区重复以上过程，直至子分区元素个数小于等于1，这体现的就是分而治之的思想（divide-and-conquer）
特点：
5. 选择最右元素作为基准点元素
6. j指针负责找到比基准点小的元素，一旦找到则与i进行交换
7. i指针维护小于基准点元素的边界，也是每次交换的目标索引
8. 最后基准点与i交换，i即为分取位置
- 选择最左元素作为基准点元素
- j指针负责从右向左找比基准点小的元素，i指针负责从左向右找比基准点大的元素，一旦找到二者交换，直至i,j相交
- 最后基准点与i（此时i与j相等）交换，i即为分区位置
package com.xzq.algorithm;
import java.util.Arrays;
public class TwoQuickSort {
public static void main(String[] args) {
int[] array = {1, 45, 87, 47, 243, 99, 67, 52, 81};
quick(array, 0, array.length-1);
System.out.println(Arrays.toString(array));
}
public static void quick(int[] array, int l, int h) {
if (l >= h) {
return;
}
int p= twoQuickSort(array, l, h); //p就表示基准点的索引位置
quick(array, l, p - 1); //循环左边分区
quick(array, p + 1, h); //循环右边分区
}
private static int twoQuickSort(int[] array, int l, int h) {
int pv = array[l]; //双边循环基准点
int j = h;
int i = l;
while (i < j) {
//j从右找小的
while (i pv) {
j--;
}
//i从左找大的
while ( i
效率比
霍尔>洛摩托
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）