八大排序-志宇

文章目录

• • 冒泡排序
  • 选择排序
  • 插入排序
  • 希尔排序
  • 堆排序
  • 大顶堆
  • 基数排序
  • 归并排序
  • 快速排序

冒泡排序

思想
比较两个相邻元素，如果顺序错误则交换过来
总共比较数组长度减一次，每次比较 将 那次比较的最大值放到符合的位置
优化: 当有一次比较，数组中没有数字交换，则证明数组已经是有序的了
图解

代码

import java.util.Arrays; //冒泡排序 public class BubbleSort {public static void main(String[] args) {//长度是5 0 1 2 3 4 int arr[] ={3, 9, -1, 10, -2};boolean flag = false;for(int i=0;i<arr.length-1;i++){for(int j=0;j<arr.length-i-1;j++){if(arr[j] > arr[j+1]){flag = true;int temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}System.out.println(Arrays.toString(arr));//在一趟排序没有发生交换则证明已经是有序的了if(flag){flag = false;}else{break;}}} }

选择排序

思想
总共比较数组长度减一次
在每次比较中记录最大的数字的位置
将每次比较出来的最大数字所在位置和符合的位置进行交换
图解

代码

import java.util.Arrays; //选择排序 public class SelectSort {public static void main(String[] args) {int[] arr={101, 34, 119, 1};for(int i=0;i<arr.length-1;i++){int min=i;for(int j=i;j<arr.length;j++){if(arr[min]> arr[j]){min=j;}}//最小值不在最小位置才交换if(min!=i){int temp=arr[i];arr[i]=arr[min];arr[min]=temp;}System.out.println(Arrays.toString(arr));}} }

插入排序

思想
好比整理扑克牌的顺序，
将要插入的牌拿出来和前一张牌比较，如果前一张牌比这张牌大 前一张牌后移， 要插入的牌再和前第二张牌比较，如果前第二张牌比这张牌大 前第二张牌后移
以此类推，直到找到符合的位置将这张牌插入
缺点
数组 arr = {2,3,4,5,6,1} 这时需要插入的数 1(最小), 这样的过程是：
{2,3,4,5,6,6}
{2,3,4,5,5,6}
{2,3,4,4,5,6}
{2,3,3,4,5,6}
{2,2,3,4,5,6}
{1,2,3,4,5,6}
结论: 当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响.
图解

代码

public class InsertSort {public static void main(String[] args) {int[] arr={101, 34, 119, 1};for(int i=1;i<arr.length;i++){//存储要插入牌的位置int index=i;//存储要插入牌的值int tempValue=arr[i];//每次是和要插入牌的值比较while(index >0 && tempValue < arr[index-1]){arr[index]=arr[index-1];index--;}if(index !=i){arr[index]=tempValue;}System.out.println(Arrays.toString(arr));}} }

希尔排序

思想
希尔排序是 快速排序 基于 分治思想 的改进
将数组分成 数组长度除二个组(gap) 每个组进行插入排序
----只要时大于等于gap的数字都要要和前面进行比较排序
再将数组分成 gap/2 个数组进行插入排序
当gap为1时进行最后一次插入排序，即可获得有序序列
图解

代码

public class ShellSort2 {public static void main(String[] args) {int[] arr={8,9,1,7,2,3,5,4,6,0};for(int gap=arr.length/2;gap>0;gap=gap/2){for(int j=gap;j<arr.length;j++){int temp=arr[j];int index=j;while(index-gap>=0 && temp<arr[index-gap]){arr[index]=arr[index-gap];index=index-gap;}if(index != j){arr[index]=temp;}}System.out.println(Arrays.toString(arr));}} }

堆排序

思想
1.将待排序序列构造成一个大顶堆
----1.1 找到完全树的最后一个叶子节点(有子节点的节点)位置为数组长度/2-1
----1.2 从数组长度/2-1向前依次进行排序
2.此时，整个序列的最大值就是堆顶的根节点。
3.将其与末尾元素进行交换，此时末尾就为最大值。
4.然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。
5.如此反复执行，便能得到一个有序序列了。
大顶堆是升序排列，小顶堆是降序排列
图解
满二叉树:
一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树
如下图: 2^3 -1=7 个节点

完全二叉树:
若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树

大顶堆

大顶堆:是完全二叉树，每个节点的值大于或等于它的左子节点和右子节点的值，没有要求结点的左子节点的值和右子节点的值的大小关系。

我们对堆中的结点按层进行编号，映射到数组中就是下面这个样子:

大顶堆特点：
arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] // i 对应第几个节点，i从0开始编号
小顶堆
小顶堆:是完全二叉树，每个节点的值小于或等于它的左子节点和右子节点的值，没有要求结点的左子节点的值和右子节点的值的大小关系。

代码

public class HeapSort2 {public static void main(String[] args) {int[] arr={4,6,8,5,9};//1.将数组调整成大顶堆//最后一个非叶子节点为 arr[arr.length/2-1]for(int i=arr.length/2-1;i>=0;i--){//将第i个非叶子节点,和子节点比较然后交换位置maxHeapSort(arr,i,arr.length);}System.out.println(Arrays.toString(arr));//每次将大顶堆的根节点和排序的最后一位交换for(int i=0;i<arr.length;i++){maxHeapSort(arr,0,arr.length-i);int temp=arr[0];arr[0]=arr[arr.length-i-1];arr[arr.length-i-1]=temp;System.out.println(Arrays.toString(arr));}}/*** * @param arr 要排序的数组* @param i 每次要排序的节点* @param length 因堆排序要每次得出最大值和排序的最后位替换,这里不用arr.length,因为长度会变化*/private static void maxHeapSort(int[] arr, int i, int length) {//保存此节点的值int temp=arr[i];//arr[2*i+1]为arr[i]的左节点for(int k=2*i+1;k<length;k=2*k+1){//判断右子节点是否存在,指针指向左右子节点中的最大值if(k+1<length && arr[k+1]>arr[k]){k++;}//判断此节点的值是否 小于 子节点中的最大值if(temp < arr[k]){//此节点等于子节点的值arr[i]=arr[k];//将此节点坐标 变成 子节的坐标,用于和下次和子节点的子节点比较i=k;}else{break;}//当for 循环结束后，我们已经将以i 为父结点的树的最大值，放在了 最顶arr[k]=temp;}} }

基数排序

思想
----计数排序：每个桶只存储单一键值；
----桶排序：每个桶存储一定范围的数值；
----基数排序：根据键值的每位数字来分配桶；
1、创建桶
----1.1如果排序是数字则创建10个桶，每个桶最大容量为序列长度
----1.2如果排序的是字母创建26个桶，每个桶最大容量为序列长度
----1.3创建一个数组用来标记每个桶中有多少个元素
2、将序列按要求放到桶中
----2.2 遍历序列中每个元素，获得指定位上的值
----2.3 根据获得指定位上的值将元素放到指定桶中，标记桶中元素个数的值增加
3、从桶中取出
----3.3按顺序遍历桶中的值，同时将值赋值给原数组
4、循环2和3最后得出有序序列
注意: 基数排序是经典的空间换时间的方式，占用内存很大, 当对海量数据排序时，容易造成 OutOfMemoryError
图解

代码

public class RadixSort2 {public static void main(String[] args) {int[]arr = {73, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 100};sort(arr,3);System.out.println(Arrays.toString(arr));}/*** @param arr 原数组 * @param i 原数组 最大数有几位数*/private static void sort(int[] arr, int length) {//创建10个一维数组,每个数组中最大有arr.length个数int[][] tempArr=new int[10][arr.length];//用来标记每个一维数组中有几个数int[] indexArr=new int[10];//循环遍历某一位for(int i=0,n=1;i<length;i++,n=n*10){//遍历数组中每个元素值放到指定桶中for(int j=0;j<arr.length;j++){//得到数组中每个元素对应的桶/*** 个位 /1 %10* 十位 /10 %10* 百位 /100 %10*/int val=arr[j]/n%10;//将元素放到指定桶,同时标记这个桶中的元素个数增加tempArr[val][indexArr[val]++]=arr[j];}int index=0;//将桶中数据放到原数组中for(int k=0;k<10;k++){for(int l=0;l<indexArr[k];l++){arr[index]=tempArr[k][l];index++;}}indexArr=new int[10];}} }

归并排序

思想
采用分治思想，将数组拆分成每一个元素，然后合并时进行排序
图解
拆分

合并
绿色数组 和 红色数组 合并为一个 蓝色数组（temp数组）
蓝色和红色数组各有一个指针，通过比较指针后移按大小顺序取出放入temp数组中

代码

public class MergeSort {public static void main(String[] args) {int[] arr={9,8,7,6,5,4,3,2,1}; //创建缓存数组int[] temp=new int[arr.length];//调用归并排序merge(arr,0,arr.length-1,temp);System.out.println(Arrays.toString(arr));}/*** 进行拆分,然后调用合并* @param arr 原数组* @param i 拆分左边界* @param j 拆分右边界* @param temp 缓冲数组*/private static void merge(int[] arr, int l, int r, int[] temp) {if(l<r){//取出中间值int mid=(l+r)/2;//拆分左面merge(arr,l,mid,temp);//拆分右面merge(arr,mid+1,r,temp);//合并mergeSort(arr,l,mid,r,temp);System.out.println(Arrays.toString(arr));}}/*** 合并* @param arr 要合并的数组* @param l 要合并的左面开始位置* @param mid 要合并的中间位置* @param r 要合并的结束位置* @param temp 缓冲数组*/private static void mergeSort(int[] arr, int l, int mid, int r, int[] temp) {int left=l; //要合并的左面数组的起始位置int right=mid+1; //要合并的右面数组的起始位置int index=l; //temp中存储数据的索引位置//一、将两个数组按大小顺序复制到temp数组中//有两个数组要合并 一个数组的位置为 [l,mid] 另一个数组的位置为[mid+1,r] while(left<=mid && right<=r){if(arr[left]<=arr[right]){temp[index]=arr[left];//缓存数组索引加1index++;//本数组索引加1left++;}else{temp[index]=arr[right];//缓存数组索引加1index++;//本数组索引加1right++;}}//将剩余的数组放到缓冲数组中while(left<=mid){temp[index]=arr[left];index++;left++;}while(right<=r){temp[index]=arr[right];index++;right++;}//二、将temp数组中的值替换给arr原数组中for(int i=l;i<=r;i++){arr[i]=temp[i];}} }

快速排序

思想
采用分治思想
1.首先选取一个基准数
2.将小于基准数的数放倒基准数的左面
3.将大于基准数的数放到基准数的右面
4.一次递归拆分，直到数组有序
图解
1.首先选取一个基准数，这里选择基准数为19
设置最左面的位置为L
设置最右面的位置为R

2.将R处索引中的8和基准数进行比较，由于比基准数小则将8放到L索引处位置，
同时L索引后移一位

3.将L处索引数值取出和基准数比较，由于比基准数大，将97放到R处索引位置，同时R索引前移一位

4.将R处索引上的值和基准数比较，由于1比基准数小，将1放到L索引位置，同时L的索引后移1位

5.将L索引处的数和基准数比较，由于9比基准数小，L直接后移一位
将L索引处的数和基准数比较，由于17比基准数小，L直接后移一位

6.在L和R重合了，这时将基准数插入到重合的位置，得到第一次排序

代码

public class QuickSort {public static void main(String[] args) {int[] arr={-9,78,0,23,-567,70};quickSort(arr,0,arr.length-1);System.out.println(Arrays.toString(arr));}private static void quickSort(int[] arr, int left, int right) {//要将所有的操作放到这个判断中,如果在这个判断外递归会出现死循环if(left<right){//选取一个基准数int pivot=arr[left];int l=left;int r=right;while (l < r){//从右往左找到一个小于基准数的数,没有找到的话R左移一位while(l<r && arr[r]>pivot){r--;}//将这个数插入到 L索引处，同时L索引坐标右移一位if(l<r){arr[l]=arr[r];l++;}//从左往右找到一个大于基准数的数,没有找到的话L右移一位while(l<r && arr[l]<pivot){l++;}//将这个数插入到 R索引处，同时R索引坐标左移一位if(l<r){arr[r]=arr[l];r--;}}//当L=R时将基准数插入到这个位置arr[l]=pivot;System.out.println(Arrays.toString(arr));quickSort(arr,left,l-1);quickSort(arr,l+1,right);}} }

总结

以上是生活随笔为你收集整理的八大排序-志宇的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。