The time complexity of various time algorithms

Bubble sort

Void bubbleSort(int pInt[], int len) {for (int i = 0; i < len - 1; ++i) {
       for (int j = i + 1; j < len; ++j) {
           if(pInt[i] > pInt[j]) { int temp = pInt[i]; pInt[i] = pInt[j]; pInt[j] = temp; //void bubbleSort1(int arr[], int len) {//for (int i = 0; i < len - 1; ++i) {       // n
//        for (int j = 0; j < len - i - 1; ++j) {   //
//            if(arr[j] > arr[j + 1]) { // int temp = arr[j]; // arr[j] = arr[j + 1]; // arr[j + 1] = temp; //} // /Copy the code

Bubble time complexity solving process

Selection sort

void select_sort(int arr[], int len) {
    for (int i = 0; i < len; ++i) {
        int min = i;
        for (int j = i + 1; j < len; ++j) {
            if(arr[min] > arr[j]) { min = j; }}if(min ! = i) {inttemp = arr[i]; arr[i] = arr[min]; arr[min] = temp; }}}Copy the code

Direct insertion sort

In the case of basic order, the most advantageous.

Insertion sort idea

 void insert_sort(int array[]) {
        int len = array.length;
        int i, j;
        for (i = 1; i < len; i++) {
            int temp = array[i];
            // make sure the point j>0 is in front of the array
            for (j = i; j > 0 && array[j - 1] > temp; j--) {
            // Move the element back to find the correct position for temp
                array[j] = array[j - 1];
            }
            array[j] = temp;
        }
        System.out.println(Arrays.toString(array));
    }
Copy the code

Hill sorting

Increase the step size based on direct insertion sort. The step is used to sort an array into a basic ordered state. At worst, this is equivalent to direct insertion sort.

void shell_sort(int arr[]) {  //
        int len = arr.length;   // len:8
        int step = len / 2;
        int i, j, k;
        while (step > 0) { // Group,
            for (i = 0; i < step; i++) {   // I is the starting position
                for (j = i + step; j < len; j += step) {// j is the end position
                    int temp = arr[j];// Save the end position, the preceding elements will be moved back
                、 for (k = j; k > i && arr[k - step] > temp; k -= step) {  // k is equal to the end position, greater than I (start position), subtract
                        arr[k] = arr[k - step];
                    }
                    arr[k] = temp;
                }
            }
            step /= 2; }}Copy the code

Hill ordering idea

Merge sort

The idea of merge sort

Break up the process

I points to the left of the cache data. J points to the mid of the cache array. K points to the left of the original array. Boundary processing ++ process left (I >mid), copy (shift) right (j), right (j>r), copy (shift) left I

      
public class MergeSort {
    public static void main(String[] args) {
        int array[] = {3.1.2.6.4.3.4.6}; 
        MergeSort javaMain = new MergeSort(); 
        javaMain.margeSort(array);
     }

    private void margeSort(int[] array) {
        int len = array.length - 1;
        margeSort_(array, 0, len);
    }
// recursively split
    private void margeSort_(int[] array, int l, int r) {
        if (l >= r) {
            return;
        }
        int mid = (l + r) >> 1;
        margeSort_(array, l, mid);
        margeSort_(array, mid + 1, r);

        if (array[mid] > array[mid + 1]) { marge(array, l, mid, r); }}private void marge(int[] array, int l, int mid, int r) {
        int temp[] = new int[r - l + 1];
        for (int i = l; i <= r; i++) {
            temp[i - l] = array[i];
        }
        // Index from the left of the original array.
        int k = l;
        // Compare two positions in the copied array, and add the smaller one to the corresponding position in the original array
        int i = l;
        int j = mid + 1;
        for (; k <= r; k++) {
            if (i > mid) {
                array[k] = temp[j - l];
                j++;
            } else if (j > r) {
                array[k] = temp[i - l];
                i++;
            } else if (array[i] > array[j]) {
                array[k] = temp[j - l];
                j++;
            } else{ array[k] = temp[i - l]; i++; }}}}Copy the code

Quick sort

You take a number, and you put anything less than this number on the left, and anything greater than this number on the right, and after a round, that number is sorted.

public class QuickSort {
    public static void main(String[] args) {
        int arr[] = {3, 1, 2, 6, 4, 3, 4, 6};
        QuickSort quickSort = new QuickSort();
        quickSort.quickSort(arr, arr.length);
        System.out.println(Arrays.toString(arr));
    }
    private void quickSort(int[] arr, int length) {
        quickSort_(arr, 0, length - 1);
    }
    private void quickSort_(int[] arr, int l, int r) {
        if (l >= r) {
            return; } int p = position(arr, l, r); quickSort_(arr, l, p); quickSort_(arr, p + 1, r); } // Using the array on the left as the standard, place greater on the right and less on the left. Private int position(int arr[], int l, int r) {int v = arr[l]; Int p = l; // Return p value, default is leftmostfor(int i = l; i <= r; I ++) {// I keeps looking for values less than v, finding no, let p swapif(arr[I] < v) {// If (arr[I] < v) {// if (arr[I] < v) { int temp = arr[i]; arr[i] = arr[p]; arr[p] = temp; }} int temp = arr[p]; arr[p] = arr[l]; arr[l] = temp;returnp; }}Copy the code

The demo github.com/eerry/werwe…