海外 酒店 网站建设,做公益筹集项目的网站,图片制作在线,快递公司网页模板八大排序算法
目录
注意#xff1a;以下排序均属于内部排序 #xff08;1#xff09;插入排序 直接插入排序 改进版本 折半插入排序 希尔排序 #xff08;2#xff09;交换排序 冒泡排序 快速排序 #xff08;3#xff09;选择排序 简单选择排序 堆排序…八大排序算法
目录
注意以下排序均属于内部排序 1插入排序 直接插入排序 改进版本 折半插入排序 希尔排序 2交换排序 冒泡排序 快速排序 3选择排序 简单选择排序 堆排序树形选择排序 4归并排序 5基数排序 排序总结分析表 一、插入排序 1. 直接插入排序
1整体思路
通过动图可以形象的理解到 1. 抽出一张牌和当前元素之前的元素逐个比较如果比当前元素小该元素就后移直到找到插入位置 2. 在无序序列中抽取一张牌通过比较插入到有序序列中
说明惯用思想初始时视第一个元素是有序的之后通过排序逐渐增大有序序列的长度
2代码实现
第一种写法while 循环更规范
public static void insert_sort(int[] arr) {/*插入排序的思想从无序的序列中拿一个数通过比较的方式插入到有序序列中初始状态假设第一个数是有序的从第二个元素开始和有序序列比较然后插入*/// 在无序序列中抽取一张牌for (int i 1; i arr.length; i) {// 记录要插入的元素值位置位于有序序列的末尾int insertvalue arr[i];// 在有序序列中从后往前和插入元素比较找到插入位置int j i - 1;/*1 2 3 9 10 15 5插入5需要插入在3的后面。所以只要插入元素比当前比较元素小就往后移*/// 推荐这种写法更规范while (j 0 insertvalue arr[j]) {arr[j 1] arr[j]; // 元素后裔j--;}// 插入元素插入到 比当前插入元素小的 元素 的后面arr[j 1] insertvalue;}
}第二种写法使用for 循环
public static void insert_sort_1(int[] arr) {// 第二种写法使用for循环for (int i 1; i arr.length; i) {int insertvalue arr[i];int j i - 1;for (; j 0; j--) {if (insertvalue arr[j]) {arr[j 1] arr[j];}else{break; // 如果 insertvalue arr[j] 就退出循环}}arr[j 1] insertvalue;}
}2. 折半插入排序
改进点使用折半查找提高效率使用循环遍历逐个匹配的效率太差 // 查找插入位置的方法采用二分思想由于查找位置的序列本身就是有序的所以可以使用二分
public static void binary_insert_sort(int[] arr) {for (int i 1; i arr.length; i) {// 初始时把第一个元素看成是有序的然后进行插入排序int insertvalue arr[i];int left 0;int right i - 1; // 和 j i -1 是等价的while (left right) {int mid left ((right - left) / 2);if (arr[mid] insertvalue) {left mid 1;} else {right mid - 1;}}// 找到了插入位置移动元素为插入做准备// 为了维持稳定性应该插入到 right 的后边// 插入位置为 right 1 , 需要把这个位置空出来才可以插入所以要取等for (int j i - 1; j right 1; j--) {arr[j 1] arr[j]; //元素后移}arr[right 1] insertvalue;}
}3. 希尔排序
动图演示 使用间隔 gapgap 逐渐递减最后 gap 的值必须是一每一轮排序对 gap 产生的序列进行排序
快速写希尔排序把直接插入排序中 “ 1 ” 的位置全部替换成 “ gap ”
/*
快速写希尔排序算法代码只要把直接插入排序中为 1 的地方全部改成 gap 即可*/
public static void shell_sort(int[] arr){// 增量序列取中间值常用方法/*增量序列是递减的并且最后一个值一定是一*/int gap arr.length / 2; // 向下取整while (gap 1) {shell(arr, gap);gap / 2;}
}// 一趟写入排序的过程
public static void shell(int[] arr, int gap){// 思想和直接插入排序不同点就在原来 “加/减一” 的位置全部变成 “gap”// 由于是分组排这里需要包含分组的第一个元素所以不加一for (int i gap; i arr.length; i) {int insertvalue arr[i];int j i - gap;// 移动元素while(j 0 insertvalue arr[j]){arr[j gap] arr[j];j - gap;}arr[j gap] insertvalue;}
}二、交换排序
1. 冒泡排序
动图演示 1普通版本
public static void bubble_sort(int[] arr){for (int i 0; i arr.length - 1; i) {for (int j 0; j arr.length - 1 - i; j) {// 前面的比后面大交换位置if(arr[j] arr[j 1]){int temp arr[j];arr[j] arr[j 1];arr[j 1] temp;}}}
}2改进版本
亮点通过变量标记的方式标记是否执行了交换操作可以一定程度上减少比较次数
// 改进版本如果本身就有序则无序交换减少比较次数
public static void bubble_sort_improve(int[] arr){for (int i 0; i arr.length - 1; i) {int flag 0; // 每次进入循环都标记为0如果有序就不交换flag 0for (int j 0; j arr.length - 1 - i; j) {// 前面的比后面大交换位置if(arr[j] arr[j 1]){flag 1; // 交换了就标记为一int temp arr[j];arr[j] arr[j 1];arr[j 1] temp;}}if(flag 0){/* 在一趟遍历之后如果都没有发生交换说明元素已经有序了后面的比较没有意义了直接退出*/break;}}
}2. 快速排序
动图演示 主要思想递归双指针对撞指针
思路分析 把第一个元素当作枢纽然后通过两个指针 left 和 right left 在前面找比枢纽大的元素搬到枢纽的后面 right 在后面找比枢纽小的元素搬到枢纽的前面 递归左右子区间 /*快速排序是冒泡排序的改进版本核心在于递归和双指针思想说明1.选取数组的第一个元素为枢纽2.left,right为数组下标3.延申可以对任意区间排序*/public static int partition(int[] arr, int left, int right) {/*双指针思想1.left指向数组的 第一个 元素从 左往右 找如果比中间值 大就搬到后面high的位置2.right指向数组的 最后一个 元素从 左右往左 找如果比中间值 小就搬到前面left的位置*/int pivot arr[left];// 两个指针的移动逐渐靠近当两个指针重合时退出循环// 此时指向的位置就是枢纽的位置while (left right) {/*注意指针的移动可能会越界需要加上判断条件 left right易错点先找小的后找大的*/// 首先在后面找小的往前搬(那对立面就是不符合要求right指针往前移)while (arr[right] pivot left right) {right--;}arr[left] arr[right];// 然后在前面找大的往后搬(那对立面就是不符合要求left指针往后移)while (arr[left] pivot left right) {left;}arr[right] arr[left];}// 此时 left right指向中间枢纽的位置放入枢纽值返回枢纽的位置arr[left] pivot;return left;
}public static void quicksort(int[] arr, int left, int right) {/*递归易错的地方需要有一个递归出口*/if(left right){int pivot partition(arr,left,right); // 首先计算枢纽值// 递归递归左子区间quicksort(arr,left,pivot - 1);// 递归排序右子区间quicksort(arr,pivot 1,right);}
}三、选择排序
1. 简单选择排序
动图演示 基本思路选一个数在这个数的后面找有没有比本身还小的有就交换位置
优化点在后面找一个最小的数避免重复的覆盖减少比较次数
区别冒泡排序的优化 冒泡排序中是比较相邻两个元素之间是否有序如果有序就不交换位置 选择排序中是在后面找一个比本身小的数然后交换位置为了避免重复的覆盖需要找到一个最小的数进行交换
1普通版本
public static void select_sort(int[] arr){for (int i 0; i arr.length; i) {for (int j i 1; j arr.length; j){if(arr[j] arr[i]){int temp arr[j];arr[j] arr[i];arr[i] temp;}}}
}2改进版本
public static void select_sort_improve(int[] arr){// 比较 n-1 趟for (int i 0; i arr.length; i) {int min_index i; // 假设当前元素是最小的记录下标// 在当前元素的后面找有没有更小的有就交换位置for (int j i 1; j arr.length; j){// 如果找到更小的就更新下标if(arr[j] arr[min_index]){min_index j;}}// 如果最小元素不是本身找到了更小的就交换位置if(min_index ! i){int temp arr[i];arr[i] arr[min_index];arr[min_index] temp;}}
}2. 堆排序二叉堆
1基本介绍 堆的性质是符合完全二叉树的在结构上是递归定义的树结构 重要性质回顾 1. 若一个非叶子节点节点的物理位置为 “ i ” 1左孩子 物理位置“ 2i ” 数组下标“ 2i 1 ” 2右孩子 物理位置“ 2i 1 ” 数组下标“ 2i 2 ” 2. 若一个数组的元素可以构成一棵树数组大小为 n 1最后一个元素叶子节点在树中的标号对应的数组下标是n / 2 2从后往前遍历的第一个非叶子节点在树中的标号对应的数组下标是[n / 2] - 1
补充关于树中节点的序号和数组下标的关系
方法从左到右从上到下依次标号
图例对应数组下标 0/ \1 2/ \ / \3 4 5 6分类 大根堆对于完全二叉树中的任意一个节点其值都大于或等于其子树中所有节点的值。这意味着大根堆的根节点是堆中最大的元素 小根堆完全二叉树中任意一个节点的值都小于或等于其子树中所有节点的值即小根堆的根节点是堆中最小的元素
大根堆示例 10/ \8 6/ \ / \5 3 2小根堆示例 1/ \3 4/ \ / \6 8 92堆排序思想 1. 构建一个大根堆 从后面的第一个非叶子节点下标n / 2 - 1开始依次递归的往上调整使得整棵树形成大根堆的结构 2. 交换最大和最小的节点重新调整堆 交换思想交换的过程就是排序的过程把最大的和最小的交换即把最大的放入有序区数组从后往前依次递减排序 调整堆思想先调整一颗树的左右孩子和根节点的大小关系构成大根堆后采用递归思想递归调整左右子树 理解在调整过程中指向的最大根节点会发生变化对根节点调整即可实现对左右子树的调整 3. 重复 2 的操作 n 个元素进行 n - 1 趟排序 关于n - 1的说明 1进行n - 1 趟排序 2循环的起始变量对应数组中最后的那个元素刚好可以和第一个元素完成交换操作最大的和最小的交换 3循环过程中刚好对应堆的大小的变化每一轮排序一个元素交换的过程堆中需要调整的元素总数减小一
堆排序代码
/*
堆排序思想又叫二叉堆
分类大顶堆小顶堆堆符合二叉树的性质说明数组的下标在树中是从上到下从左到右依次编号的排序过程说明1. 构建一个大顶堆每次交换最小和最大的并且堆大小缩小减一
2. 交换的过程把最大的放在有序区但是破坏了大顶堆的结构需要重新调整堆3. 有序的过程把最大的放在有序区数组从后往前一次放入有序元素完成排序*/// 堆调整大顶堆
// n表示数组的大小i表示最大值的下标索引
public static void heapify(int[] arr, int n, int i) {/*易错这里表示的下标值然而二叉树中的性质指的是物理位置数组是从0开始编号的举例说明7/ \6 57下标索引是06按照物理位置计算方法左孩子2 * i 0结果还是0但是下标索引是1得出的关系在物理位置的基础上加一才是索引下标*/int max_index i; // 初始化最大值下标索引int left 2 * i 1; // 左孩子的下标索引int right 2 * i 2; // 右孩子的下标索引// 和左右孩子比较更新最大值下标索引// 注意防止越界需要加上限制条件if (left n arr[left] arr[max_index]) {max_index left;}if (right n arr[right] arr[max_index]) {max_index right;}// 如果最大值不是初始化的值说明找到了更大的值把最大值放到根节点if (max_index ! i) {int temp arr[i];arr[i] arr[max_index];arr[max_index] temp;// 递归调整左右子树max_index在这个过程中做了更新heapify(arr, n, max_index);}
}//堆排序
public static void heap_sort(int[] arr) {/*7/ \6 5/ \ / \4 3 2 1总节点数7循环起点7/2 - 1 3 - 1 2即下标为2的元素开始元素5*/// 构建大顶堆如果每一个子树都是大顶堆则整个二叉堆就是大顶堆int n arr.length;// 从最后一个非叶子节点开始向上进行堆调整for (int i n / 2 - 1; i 0; i--) {heapify(arr, n, i);}// 排序过程交换元素调整堆进行 n - 1 趟排序// 初值每交换一次可以理解为排序一个元素则堆中需要排序的元素总数减少一// 初值为 i -1 正好对应最后一个元素的下标方便交换for (int i n - 1; i 0; i--) {// 把最大的和最小的进行交换int temp arr[0];arr[0] arr[i];arr[i] temp;// 交换后破坏了大顶堆的结构重新调整堆排序的过程中堆的大小在递减heapify(arr, i, 0);}
}四、归并排序
动图演示 思路运用合并为有序序列的思想、递归思想两个有序序列通过比较的方式合并成一个更长的有序序列而比较的过程正好是排序的过程
小结排序左区间排序右区间两个区间合并然而排序的过程又是两个区间合并的过程即采用递归思想
归并排序代码 五、基数排序
