java中常用的排序和查找算法

绝地灬酷狼 2022-06-07 03:41 183阅读 0赞

本文内容来自网络资源整理，若有错误，敬请指正。

#### java中的常用排序方法 ####

java中常用的几种排序方法：选择排序、插入排序、快速排序、冒泡排序、归并排序、shell排序。  
java 中的查找方法有：顺序查找法、二分查找法

##### 选择排序 #####

思路：在乱序数组中，假设第一位数最小，依次让后面的数与之比较，若遇到比它小的数就交换位置，一趟下来第一个数就是序列中最小的数，然后从第二个数开始重复操作。

public static void selectSort(int[] array) {  
            int position = 0;  
            for (int i = 0; i < array.length; i++) {  
                int j = i + 1;  
                position = i;  
                int temp = array[i];  
                for (; j < array.length; j++) {  
                    if (array[j] < temp) {  
                        temp = array[j];  
                        position = j;  
                    }  
                }  
                array[position] = array[i];  
                array[i] = temp;  
            }  
            System.out.println(Arrays.toString(array) + " selectSort");  
        }

##### 插入排序 #####

思路：如同玩扑克牌一样，每次摸牌都将它与手中的牌比较，始终将牌放在比它大的牌前面，比它小的牌后面。这样当牌全部摸到手上后，就是一个有序的序列。

public static void insertSort(int[] array) {  
         for (int i = 1; i < array.length; i++) {  
             int temp = array[i];  
             int j = i - 1;  
             for (; j >= 0 && array[j] > temp; j--) {  
                 //将大于temp的值整体后移一个单位 
                 array[j + 1] = array[j];  
             }  
             array[j + 1] = temp;  
         }  
         System.out.println(Arrays.toString(array) + " insertSort");  
     }

##### shell排序 #####

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。  
希尔排序是基于插入排序的以下两点性质而提出改进方法的：  
插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；  
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。  
先取一个正整数d1 < n, 把所有相隔d1的记录放一组，每个组内进行直接插入排序；然后d2 < d1，重复上述分组和排序操作；直至di = 1，即所有记录放进一个组中排序为止。

![shell][]

public static void shellSort(int[] array) {  
            int i;  
            int j;  
            int temp;  
            int gap = 1;  
            int len = array.length;  
            while (gap < len / 3) { gap = gap * 3 + 1; }  
            for (; gap > 0; gap /= 3) {  
                for (i = gap; i < len; i++) {  
                    temp = array[i];  
                    for (j = i - gap; j >= 0 && array[j] > temp; j -= gap) {  
                        array[j + gap] = array[j];  
                    }  
                    array[j + gap] = temp;  
                }  
            }  
            System.out.println(Arrays.toString(array) + " shellSort");  
        }

##### 冒泡排序 #####

思路：在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。  
代码：

public static void bubbleSort(int[] array) {  
            int temp = 0;  
            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]) {  
                        temp = array[j];  
                        array[j] = array[j + 1];  
                        array[j + 1] = temp;  
                    }  
                }  
            }  
            System.out.println(Arrays.toString(array) + " bubbleSort");  
        }

##### 快速排序 #####

快速排序是排序方法里面速率最快的一种方法，是对冒泡排序的一种改进， 属于不稳地排序。  
![快速排序图][1347009479_6587.jpg]

public static void quickSort(int[] array) {  
        _quickSort(array, 0, array.length - 1);  
        System.out.println(Arrays.toString(array) + " quickSort");  
    }  
    
    
    private static int getMiddle(int[] list, int low, int high) {  
        int tmp = list[low];    //数组的第一个作为中轴 
        while (low < high) {  
            while (low < high && list[high] >= tmp) {  
                high--;  
            }  
    
    
            list[low] = list[high];   //比中轴小的记录移到低端 
            while (low < high && list[low] <= tmp) {  
                low++;  
            }  
    
    
            list[high] = list[low];   //比中轴大的记录移到高端 
        }  
        list[low] = tmp;              //中轴记录到尾 
        return low;                  //返回中轴的位置 
    }  
    
    
    private static void _quickSort(int[] list, int low, int high) {  
        if (low < high) {  
            int middle = getMiddle(list, low, high);  //将list数组进行一分为二 
            _quickSort(list, low, middle - 1);      //对低字表进行递归排序 
            _quickSort(list, middle + 1, high);      //对高字表进行递归排序 
        }  
    }

##### 归并排序 #####

思路：归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。  
![归并排序][1347009541_6721.jpg]

代码：

public static void mergingSort(int[] array) {  
            sort(array, 0, array.length - 1);  
            System.out.println(Arrays.toString(array) + " mergingSort");  
        }  
    
        private static void sort(int[] data, int left, int right) {  
            if (left < right) {  
                //找出中间索引 
                int center = (left + right) / 2;  
                //对左边数组进行递归 
                sort(data, left, center);  
                //对右边数组进行递归 
                sort(data, center + 1, right);  
                //合并 
                merge(data, left, center, right);  
            }  
        }  
    
        private static void merge(int[] data, int left, int center, int right) {  
            int[] tmpArr = new int[data.length];  
            int mid = center + 1;  
            //third记录中间数组的索引 
            int third = left;  
            int tmp = left;  
            while (left <= center && mid <= right) {  
                //从两个数组中取出最小的放入中间数组 
                if (data[left] <= data[mid]) {  
                    tmpArr[third++] = data[left++];  
                } else {  
                    tmpArr[third++] = data[mid++];  
                }  
            }  
    
            //剩余部分依次放入中间数组 
            while (mid <= right) {  
                tmpArr[third++] = data[mid++];  
            }  
    
            while (left <= center) {  
                tmpArr[third++] = data[left++];  
            }  
    
            //将中间数组中的内容复制回原数组 
            while (tmp <= right) {  
                data[tmp] = tmpArr[tmp++];  
            }  
        }

##### shell排序 #####

![shell排序][shell]

代码：

#### 查找算法 ####

java中常用的查找算法有顺序查找和二分查找。顺序查找也许效率较低，二分查找效率高，但是要在序列是在有序的情况下。顺序查找这里不在赘述。

##### 二分查找 #####

前提条件：已排序的数组中查找

二分查找的基本思路是：首先确定该查找区间的中间点位置： int mid = (low+upper) / 2；然后将待查找的值与中间点位置的值比较：若相等，则查找成功并返回此位置。若中间点位置值大于待查值，则新的查找区间是中间点位置的左边区域。若中间点位置值小于待查值，则新的查找区间是中间点位置的右边区域。下一次查找是针对新的查找区间进行的。

图例说明：

原始数据： int\[\] a=\{5,3,6,1,9,8,2,4,7\}; 查找是否存在数字8；

第一步，先用之前学过的排序方法将数组按升序排序：int\[\] a=\{1,2,3,4,5,6,7,8,9\};

第二步，取中间数：5跟8比较，8大于5 ，取中间数右侧的数组进行比较，即\{6,7,8,9\}

第三步：重复第一步和第二步，直到找到数据或者比较完所有数据。

代码：

import java.util.Scanner;
    /* * 二分查找 */
    public class BinarySearch {
        public static void main(String[] args) {
            int[] arr={
       5,3,6,1,9,8,2,4,7};
            //先打印输出原始数组数据
            System.out.println("原始数组数据如下：");
            for (int n : arr) {
                System.out.print(n+" ");
            }
            System.out.println();
            //首先对数组进行排序，这里用冒泡排序
            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;
                    }
                }
            }
            //遍历输出排序好的数组
            System.out.println("经过冒泡排序后的数组：");
            for(int n:arr){
                System.out.print(n+" ");
            }
            System.out.println();//换行
            Scanner input=new Scanner(System.in);
            System.out.println("请输入你要查找的数：");
            int num=input.nextInt();
            int result=binarySearch(arr, num);
            if(result==-1){
                System.out.println("你要查找的数不存在……");
            }
            else{
                System.out.println("你要查找的数存在，在数组中的位置是："+result);
            }
        }
        //二分查找算法
        public static int binarySearch(int[] arr,int num){
    
            int low=0;
            int upper=arr.length-1;
            while(low<=upper){
                int mid=(upper+low)/2;
                if(arr[mid]<num){
                    low=mid+1;
                }
                else if(arr[mid]>num){
                    upper=mid-1;
                }
                else
                    return mid;
            }
            return -1;
        }
    }

[shell]: /images/20220607/43d362d63cb744da9a2764dd7fe5ea4a.png
[1347009479_6587.jpg]: https://img-my.csdn.net/uploads/201209/07/1347009479_6587.jpg
[1347009541_6721.jpg]: https://img-my.csdn.net/uploads/201209/07/1347009541_6721.jpg