经典排序算法

骑猪看日落 2023-07-17 06:27 89阅读 0赞

## 冒泡排序 ##

//关键代码
        public static void sort(int array[]) {
            for (int i = 0; i < array.length - 1; i++) {
                boolean flag = false;
                for (int j = 0; j < array.length - 1 - i; j++) {
                    if (array[j] > array[j + 1]) {
                        swap(array, j, j + 1);
                        flag = true;
                    }
                }
                if (!flag) {
                    break;
                }
            }
        }
        //交换位置
        public static void swap(int[] array, Integer i, Integer j) {
            Integer temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }

外层循环控制次数，内层循环控制相邻的两个数之间的比较。如果符合条件，则交换位置。同时在内层循环之外设置一个变量flag。如果发生交换，则将flag置为true。否则，说明本次循环的时候，每两个相邻的数之间都是有序的，数组已经排好序。此时将flag置为false，直接退出循环。

## 插入排序 ##

public static void sort(int[] array) {
            for (int i = 1; i < array.length; i++) {
                int temp = array[i];
                int index = i - 1;
                //如果需要插入的值小于他前面的数
                while (index >= 0 && array[index] > temp) {
                    array[index + 1] = array[index];
                    index--;
                }
                array[index + 1] = temp;
            }
        }

从数组的第二个位置开始，依次根前面的数字比较，如果前面的数大于本数，则将前面的数字后移一位。直到前面的数不大于本数字或者index<0，此时，index代表前面的数字的位置（或者index<0）,所以需要将这个数字插入到index++的位置。

## 希尔排序 ##

希尔排序是在插入排序的基础之上进行的

private static void sort(int array[]){
            //设置步长，也即是将整个数组分为步长（n）个部分
            int grap=array.length/2;
            //如果上次分完之后数组分组不是1，则进行循环
            while(grap>0){
                //比较每一个分组里面的数据，进行插入排序
                for(int i=grap ; i<array.length ; i++){
                    int j = i-grap;
                    int temp = array[i];
                    while(j>=0 && array[j]>temp){
                        array[j+grap]=array[j];
                        j-=grap;
                    }
                    array[j+grap]=temp;
                }
                //更新步长
                grap/=2;
            }
        }

## 选择排序 ##

public static void sort(int array[]) {
            int index = 0;
            int min = 0;
            for (int i = 0; i < array.length - 1; i++) {
                index = i;
                min = array[i];
                for (int j = i + 1; j < array.length; j++) {
                    if (array[j] < min) {
                        index = j;
                        min = array[j];
                    }
                }
                if (index != i) {
                    array[index] = array[i];
                    array[i] = min;
                }
            }
        }

先将第一个值设置为最小的，然后遍历数组，找到比他小的，则更新最小值，遍历完之后，交换位置。然后开始下一轮，寻找次小值，以此类推。

## 快速排序 ##

private static void sort(int array[], Integer left, Integer right) {
            if(left<right){
                int midNum=getPartion(array,left,right);
                sort(array,left,midNum-1);
                sort(array,midNum+1,right);
            }
        }
        private static Integer getPartion(int arr[] , Integer left,Integer right){
            //中轴值
            int key=arr[left];
            while(left<right) {
                //从右向左找比中轴值小的数
                while(left<right && arr[right]>=key) {
                    right--;
                }
                //将找到的大的数 填充到左边的坑
                arr[left]=arr[right];
                //从左向右找比中轴值大的数
                while(left<right && arr[left]<=key) {
                    left++;
                }
                //将找到的小的数填充到右边的坑
                arr[right]=arr[left];
            }
            arr[left]=key;
            return left;
        }

## 归并排序 ##

public static void deMerge(int[] array, int left, int right, int[] temp) {
            if (left < right) {
                int mid = (left + right) / 2;
                deMerge(array, left, mid, temp);
                deMerge(array, mid + 1, right, temp);
                merge(array, left, mid, right, temp);
            }
        }
        public static void merge(int[] array, int left, int mid, int right, int[] temp) {
            int i = left;
            int j = mid + 1;
            int t = 0;
            while (i <= mid && j <= right) {
                if (array[i] <= array[j]) {
                    temp[t] = array[i];
                    i++;
    
                } else {
                    temp[t] = array[j];
                    j++;
                }
                t++;
            }
            while (i <= mid) {
                System.out.println(i+":i");
                temp[t] = array[i];
                i++;
                t++;
            }
            while (j <= right) {
                temp[t] = array[j];
                j=j+1;
                t++;
            }
            t = 0;
            int leftTemp = left;
            while (leftTemp <= right) {
                array[leftTemp] = temp[t];
                t++;
                leftTemp++;
            }
        }