十大排序算法

一、排序算法

1、冒泡排序

依次比较相邻元素的大小

public static void 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 sort(int arr[]){
        for (int i = 0 ;i<arr.length-1;i++){
            for (int j = i+1; j <arr.length; j++) {
                if(arr[i]>arr[j]){
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }

3、插入排序

将数组分为有序表（第一次只包含数组下标为0的一个元素）和无序表，从无序表中选取第一个元素插入到有序表的对应位置。

方法一

public static void sort(int arr[]){
        for (int i = 1; i < arr.length; i++) {
            if(arr[i]<arr[i-1]){
                int temp = arr[i];
                for (int j = i-1; j >= 0; j--) {
                    if(arr[j]>temp){
                        arr[j + 1] = arr[j];
                    }else{
                        break;
                    }
                    arr[j] = temp;
                }
            }
        }
    }

方法二

public static void sort(int arr[]){
        for (int i = 1; i < arr.length; i++) {
            int insertVal = arr[i];
            int insertIndex = i-1;
            while(insertVal<arr[insertIndex] && insertIndex>=0){
                arr[insertIndex + 1] = arr[insertIndex];//比插入值大的元素后移一位
                insertIndex--;
            }
            if(insertIndex+1 != i){
                arr[insertIndex + 1] = insertVal;
            }
        }
    }

4、希尔排序

分组的插入排序

public static void shellSort2(int []arr) {
        //定义一个变量用于交换值
        int temp=0;
        //gap为步长，每次步长为上一次的1/2，通过步长将数组分组
        for(int gap=arr.length/2;gap>0;gap/=2) {
            //i为数组中第一个步长之后的数据
            for(int i=gap;i<arr.length;i++) {
                int j=i;
                temp=arr[j];
                //同插入排序，需要插入的值从后往前依次比较，找到插入的位置，
                while(j-gap>=0 && temp<arr[j-gap]) {
                    arr[j]=arr[j-gap];
                    j=j-gap;
                }
                arr[j]=temp;
            }
        }
    }

5、快速排序

以数组的第一个元素为标准数，比标准数小的放在左边，比标准数大的数放在右边

然后以标准数分组递归。

public static void sort(int arr[],int start ,int end){
        if(start<end){
            int sign = arr[start];
            int low = start;
            int high = end;
            while(low<high){
                while(low<high && arr[high]>=sign){
                    high--;
                }
                arr[low] = arr[high];
                while(low<high && arr[low]<=sign){
                    low++;
                }
                arr[high] = arr[low];
            }
            arr[low] = sign;
            sort(arr,start,low-1);
            sort(arr,low+1,end);
        }
    }

6、基数排序

空间换时间的经典算法，将所有数统一为相同的长度，数位短的前面补零。然后从最低位开始排序，依次到最高位。

public static void sort(int arr[]){
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if(arr[i]>max){
                max = arr[i];
            }
        }
        int maxLength = (max + "").length();
        //定义一个二维数组，表示10个桶，每个桶就是一个数组
        int[][] bucket = new int[10][arr.length];
        //定义一个一维数组记录每个桶存放的数据个数。
        int[] elementsCount = new int[10];
        //数据存入桶中
        for (int i = 0, n=1; i < maxLength; i++,n=n*10) {
            for(int j=0;j<arr.length;j++){
                int element = arr[j] / n % 10;
                bucket[element][elementsCount[element]] = arr[j];
                elementsCount[element]++;
            }
            //从桶中取出数据
            int index = 0;
            for (int k = 0; k < 10; k++) {
                if(elementsCount[k]!=0){
                    for (int m = 0; m <elementsCount[k] ; m++) {
                        arr[index++] = bucket[k][m];
                    }
                }
                //将对应桶的计数清零
                elementsCount[k] = 0;
            }
        }
    }

二、二分查找

 public static int search(int arr[],int target){
        int left = 0;
        int right = arr.length-1;
        while(left<right){
            int mid = (right+left)/2;
            if(arr[mid]==target){
                return mid;
            }else if(arr[mid]<target){
                left = mid+1;
            }else{
                left = mid + 1;
            }
        }
        return -1;
    }