JAVA 排序与二分查找

谁践踏了优雅 2022-05-04 08:30 210阅读 0赞

## 排序与二分查找 ##

# 冒泡排序 #

排序思想：从前往后将相邻的两个元素进行比较，则第一次比较完成后，最后一个元素一定是数值最大的。依次重复，每一轮比较就会将剩余元素中的最大一个移到最后边(不包括已经比较成功的数据。)

![在这里插入图片描述][70]

public class Sort{ 
        public static void main(String[] args) { 
            int[] a={ 9,8,7,6,5,4,3,2,1,0};
            maopao(arrays);
            System.out.println(Arrays.toString(a));
        }
        public static void maopao(int[] a) { 
            for(int i=0;i<a.length;i++)
                for(int j=0;j<a.length-i-1;j++)
                    if(a[j]>a[j+1]) { 
                        int t=a[j];
                        a[j]=a[j+1];
                        a[j+1]=t;
                     }
    
    }

# 插入排序 #

排序思想：每次从数组序列中拿出一个元素，与有序序列从后往前比较，找到合适的位置插入即可。每次插入完成后有序序列依然有序。  
例如:  
49,38,65,97,76,13,27 原始数据  
\[49\],38,65,97,76,13,27 从1索引开始插入  
\[38,49\], ,65,97,76,13,27  
\[38,49,65\] 97,76,13,27  
\[38,49,65,97\] 76,13,27  
\[38,49,65,76,97\]13,27  
\[13,27,38,49,65,76,97\],27  
\[13,27,38,49,65,76,97\]

public class test{ 
        public static void main(String[] args) { 
            //直接插入排序
            int[] arr = { 10, 9, 6, 8, 7, 5, 4, 3, 1, 2, 20, 25, 30, 65};
            // [9,10]
            //插入排序
            insertSort(arr);
            System.out.println(Arrays.toString(arr));
        }
        private static void insertSort(int[] arr) { 
            //外层循环 是循环的轮次
            for (int i = 1; i <= arr.length - 1; i++) { 
                //当前元素,如果小于我前面的元素,交换位置
                int j = i;
                int temp=arr[i];
                while (j > 0 && arr[j] < arr[j - 1]) {  
                    arr[j] = arr[j - 1];
                    j--;
                }
                a[j]=temp;
            }
        }

# 选择排序 #

排序思想：每次从剩下的元素中选出最小的一个元素放在第一个位置，然后从下一个元素开始，继续选出最小的一个元素放在第一个位置(除去已经排好序的）。  
![70 1][]

public class xuanze{ 
        public static void main(String[] args) { 
            int[] arrays = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
            paixu(arrays);
            System.out.println(Arrays.toString(arrays));
        }
        public static void paixu(int[] a) { 
             int index;
            for (index = 0; index < a.length-1; index++) { 
                int min = index;
                for (int i = index+1; i < a.length;i++)
                    if (a[min] >= a[i])
                        min = i;
                if(index!=min)
                { 
                    int t = a[index];
                    a[index] = a[min];
                    a[min] = t;
                }
            }
    }

# 快排 #

快排思想：  
1从数组中取出一个数，作为基准数。  
2分区：将比这个数大或等于的数全放到他的右边，小于他的数  
全放到他的左边。  
3.再对左右区间重复第二步，直到各区间只有一个数。

先取出第一个数作为基数，使用j从后往前遍历遇到比这个数小的数则将这个数放在基数位置，再用i从前往后遍历遇到比基数大的放在j的位置，在继续用j从后往前遍历，依次循环，每一次找到一个要移动的数都会换边继续遍历，知道i与j相等。  
此时将基数放在i的位置，而基数左边的都是比基数小的，基数右边都是比基数大的。  
再将基数左边与基数右边的数按照此算法继续排序，知道每部分都只有一个数，则此数组为有序数组。

public class kuaipai { 
    
        public static void main(String[] args) { 
            int[] arr = { 57,6,767,43245,765,76573,53,23,124,6,54};
            ssort(arr, 0, arr.length - 1);
            System.out.println(Arrays.toString(arr));
    
        }
        public static void ssort(int[] array,int star,int end){ 
            if(star<end){ 
                int index=getIndex(array,star,end);//找到基数下标
                ssort(array,star,index-1);//将基数左边排序
                ssort(array,index+1,end);//将基数右边排序
            }
        }
        public static int getIndex(int[] array,int star,int end){ 
            int i=star;
            int j=end;
            int x=array[i];
            while(i<j){ 
                while(i<j&&array[j]>=x)//遍历右边，找到比基数小的元素
                    j--;
                if(i<j){ //移动该元素
                    array[i]=array[j];
                    i++;
                }
                while(i<j&&array[i]<x)//遍历左边，找到比基数大的元素
                       i++;
                if(i<j){ //移动该元素
                    array[j]=array[i];
                    j--;
                }
            }
            array[i]=x;将基数填到中间。
            return i;
        }
    }

## 二分查找 ##

前提：数组有序  
思想：每次讲要查找的数与中间元素比较，要是小于中间元素则在左边查找，要是大于中间元素，则在右边查找。  
![在这里插入图片描述][70 2]

public class erfenfa { 
        public static void main(String[] args) { 
            int[] arrays={ 1,2,3,4,5,6,7,8,9,10};
            System.out.println(find(arrays,0,arrays.length-1,-8));
    
        }
        public static int find(int[] arrays,int a,int b,int n)
        { 
            int mid=(a+b)/2;
            if(a>b)
                return -1;
            else if(arrays[mid]>n)
                return find(arrays ,a,mid-1,n);
            else if(arrays[mid]<n)
                return find(arrays,mid+1,b,n);
            else
                return mid;
        }
    }

[70]: /images/20220504/eb74f978936249389775dc4a4c8c6101.png
[70 1]: /images/20220504/88d0a79f89e547b2adfdde9f7fdd9b5a.png
[70 2]: /images/20220504/19e62422729a480fba9030cbb8cd2ebc.png