【排序】基本排序的介绍

冒泡和插入排序和快排

这三种排序感觉比较常见面试也容易问到

1、冒泡排序

简单的来说就是将大的数和前面的数比较，交换，一直冒泡到最上方，然后下一次冒泡忽略这个上次的最大值就好了。

代码如下:

package sort;


public class bubble_sort {
    public void bubble_sort(int[] number) {
        for (int i = 0; i < number.length; i++) {
            for (int j = 0; j < number.length - i - 1; j++) {
                if(number[j] > number[j+1]) {
                    int temp = number[j];
                    number[j] = number[j+1];
                    number[j+1] = temp;
                }
            }
        }
    }


    public static void main(String[] args) {
        bubble_sort sort = new bubble_sort();
        int[] a = {3,2,1,4,5};
        sort.bubble_sort(a);
        for(int i : a) {
            System.out.print(i + " ");
        }
    }
}

2、插入排序

插入排序顾名思义就是找到每一个数字需要插入的地方，保证这个数字插入完后前面的都是有序的就好了，那实现思路将每个数左边的数遍历过去，腾出位置给这个数插入就好了。

package sort;


public class Insert_sort {
    public void insertSort(int[] arr) {
        int i,j;
        for(i = 1; i < arr.length; i++) {
            int temp = arr[i];
            for(j = i - 1; j >= 0; j--) { //这个数前面的数，注意要从后往前，不然前面的往后挪就覆盖了，从后开始往后挪没事有temp呢
                if(temp < arr[j]) {
                    arr[j + 1] = arr[j];
                } else {
                    break;
                }
            }
            arr[j + 1] = temp;
        }
    }


    public static void main(String[] args) {
        Insert_sort insert_sort = new Insert_sort();
        int[] arr = {3, 2, 1, 4, 5};
        insert_sort.insertSort(arr);
        for(int i : arr) {
            System.out.print(i + " ");
        }
    }
}

3、快排

说实话，复习了很多次，但是呢不做笔记总忘记，思路相信还是一直记得住的，就是一次循环做到数组左边的数都小于基准值，数组右边的数大于基准值。

假如说，以数组第一个值为基准值，实现思路就是右边依次找比基准值小的，找到暂停，左边依次找比基准值大的，找到暂停，然后交换值就好了，如果两边没有相遇就继续找，继续交换，直到相遇i = j。 为什么从右边开始找，因为基准值在左边。

然后通过递归把左边的子数组和右边的子数组都放进去就好了，能够实现所有的都是左边小右边大，即有序了。

package sort;


import java.lang.reflect.Array;


public class Qucik_sort {
    public void qucick_sort(int []arr, int low, int high) {
        int i = low,j = high,flag; // i 左边的，j右边的，flag为基准值
        if(low >= high) {
            return;
        }
        flag = arr[low];
        while(i < j) {
            while (flag <= arr[j] && i < j) {
                j--;
            }
            while (flag >= arr[i] && i < j) {
                i++;
            }
            if(i < j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        arr[low] = arr[i]; //将基准值放到应该去的中间位置
        arr[i] = flag;
        qucick_sort(arr,low,j - 1); //这里用i也是一样的
        qucick_sort(arr,j + 1, high);
    }


    public static void main(String[] args) {
        Qucik_sort qucik_sort = new Qucik_sort();
        int[] arr = {3, 2, 1, 4, 5};
        qucik_sort.qucick_sort(arr,0,4);
        for(int i : arr) {
            System.out.print(i + " ");
        }
    }
}