How to use the seven sorting methods of Java data structures

##1. Insertion sort

1. Direct insertion sort

When inserting the i-th (i>=1) element, The previous array[0], array[1],..., array[i-1] have been sorted. At this time, use array[i] and array[i-1], array[i-2],... Compare, find the insertion position, insert array[i], and move the elements at the original position backward.

The closer the data is to order, the less time it takes to insert sort directly.

Time complexity: O(N^2)

Space complexity O(1), is a stable algorithm

Direct insertion sort:

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

2. Hill sorting

The basic idea of ​​Hill sorting method is: first select an integer gap, and divide all records in the file to be sorted into gap groups , all the numbers with a distance of gap are in the same group, and the numbers in each group are directly inserted and sorted. Then take gap=gap/2 and repeat the above grouping and sorting work. When gap=1, all numbers are sorted directly within a group.

• Hill sort is an optimization of direct insertion sort.

• The purpose is to make the array closer to order, so pre-sorting is performed when gap > 1. Insertion sort can quickly sort a nearly ordered array when the gap is 1.

• The time complexity of Hill sorting is difficult to calculate, because there are many ways to obtain gap values, making it difficult to calculate.

Hill sorting:

public static void shellSort(int[] array){
        int size=array.length;
        //这里定义gap的初始值为数组长度的一半
        int gap=size/2;
        while(gap>0){
            //间隔为gap的直接插入排序
            for (int i = gap; i < size; i++) {
                int tmp=array[i];
                int j=i-gap;
                for(;j>=0;j-=gap){
                    if(array[j]>tmp){
                        array[j+gap]=array[j];
                    }else{
                        break;
                    }
                }
                array[j+gap]=tmp;
            }
            gap/=2;
        }
    }

2. Selection sorting

1. Selection sorting

• Select the smallest data element in the element set array[i]--array[n-1]

• If it is not the first element in this set of elements one, then exchange it with the first element in this set of elements

• In the remaining set, repeat the above steps until there is 1 element left in the set

Time complexity: O(N^2)

Space complexity is O(1), unstable

Selection sort:

    //交换
    private static void swap(int[] array,int i,int j){
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;
    }
    //选择排序
    public static void chooseSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            int minIndex=i;//记录最小值的下标
            for (int j = i+1; j < array.length; j++) {
                if (array[j]<array[minIndex]) {
                    minIndex=j;
                }
            }
            swap(array,i,minIndex);
        }
    }

2. Heap sorting

Two ideas for heap sorting (taking ascending order as an example):

• Create a small root heap, in order Take out the top element of the heap and put it into the array until the heap is empty

• Create a large root heap, define the tail element position key of the heap, and exchange the top element of the heap and the element at the key position each time (key --), until the key reaches the top of the heap. At this time, the sequential traversal of the elements in the heap is in ascending order (as follows)

Time complexity: O(N^2)

Space complexity: O(N), unstable

Heap sort:

    //向下调整
    public static void shiftDown(int[] array,int parent,int len){
        int child=parent*2+1;
        while(child<len){
            if(child+1<len){
                if(array[child+1]>array[child]){
                    child++;
                }
            }
            if(array[child]>array[parent]){
                swap(array,child,parent);
                parent=child;
                child=parent*2+1;
            }else{
                break;
            }
 
        }
    }
    //创建大根堆
    private static void createHeap(int[] array){
        for (int parent = (array.length-1-1)/2; parent >=0; parent--) {
            shiftDown(array,parent,array.length);
        }
    }
    //堆排序
    public static void heapSort(int[] array){
        //创建大根堆
        createHeap(array);
        //排序
        for (int i = array.length-1; i >0; i--) {
            swap(array,0,i);
            shiftDown(array,0,i);
        }
    }

3. Exchange sort

1 , Bubble sorting

Two-level loops, the first-level loop indicates the number of times to be sorted, and the second-level loop indicates the number of comparisons to be made in each pass; the bubble sorting here has been optimized, and in each pass When comparing, we can define a counter to record the number of data exchanges. If there is no exchange, it means that the data is already in order and no further sorting is needed.

Time complexity: O(N^2)

Space complexity is O(1), which is a stable sorting

Bubble sorting:

   public static void bubbleSort(int[] array){
        for(int i=0;i<array.length-1;++i){
            int count=0;
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j]>array[j+1]){
                    swap(array,j,j+1);
                    count++;
                }
            }
            if(count==0){
                break;
            }
        }
    }

2. Quick sort

Take any element in the sequence of elements to be sorted as the base value, and divide the set to be sorted into two subsequences according to the sorting code. All elements in the left subsequence are less than the base value, all elements in the right subsequence are greater than the base value, and then the process is repeated for the left and right subsequences until all elements are arranged in the corresponding positions.

Time complexity: Best O (N*Logn): You can try to uniformly divide the sequence to be sorted at each time. Ordered

Space complexity: best O(logn), worst O(N). Unstable sorting

(1) Pit digging method

When the data is in order, quick sorting is equivalent to a binary tree without left or right subtrees. At this time, the space complexity will reach O(N), if a large amount of data is sorted, it may cause a stack overflow.

public static void quickSort(int[] array,int left,int right){
        if(left>=right){
            return;
        }
        int l=left;
        int r=right;
        int tmp=array[l];
        while(l<r){
            while(array[r]>=tmp&&l<r){
            //等号不能省略，如果省略，当序列中存在相同的值时，程序会死循环
                r--;
            }
            array[l]=array[r];
            while(array[l]<=tmp&&l<r){
                l++;
            }
            array[r]=array[l];
        }
        array[l]=tmp;
        quickSort(array,0,l-1);
        quickSort(array,l+1,right);
    }

(2) Optimization of quick sort

Choose the key using the middle method of three numbers

Regarding the selection of key values, if the sequence to be sorted is in order, then we Selecting the first or last key as the key may cause the left or right side of the split to be empty. In this case, the space complexity of quick sort will be relatively large and it is easy to cause stack overflow. Then we can use the three-number method to cancel this situation. The middle value of the first, last and middle element in the sequence is used as the key value.

 //key值的优化，只在快速排序中使用，则可以为private
    private int threeMid(int[] array,int left,int right){
        int mid=(left+right)/2;
        if(array[left]>array[right]){
            if(array[mid]>array[left]){
                return left;
            }
            return array[mid]<array[right]?right:mid;
        }else{
            if(array[mid]<array[left]){
                return left;
            }
            return array[mid]>array[right]?right:mid;
        }
    }

When recursing into a small subrange, you can consider using insertion sort

随着我们递归的进行，区间会变的越来越小，我们可以在区间小到一个值的时候，对其进行插入排序，这样代码的效率会提高很多。

（3）快速排序的非递归实现

 //找到一次划分的下标
    public static int patition(int[] array,int left,int right){
        int tmp=array[left];
        while(left<right){
            while(left<right&&array[right]>=tmp){
                right--;
            }
            array[left]=array[right];
            while(left<right&&array[left]<=tmp){
                left++;
            }
            array[right]=array[left];
        }
        array[left]=tmp;
        return left;
    }
    //快速排序的非递归
    public static void quickSort2(int[] array){
        Stack<Integer> stack=new Stack<>();
        int left=0;
        int right=array.length-1;
        stack.push(left);
        stack.push(right);
        while(!stack.isEmpty()){
            int r=stack.pop();
            int l=stack.pop();
            int p=patition(array,l,r);
            if(p-1>l){
                stack.push(l);
                stack.push(p-1);
            }
            if(p+1<r){
                stack.push(p+1);
                stack.push(r);
            }
        }
    }

四、归并排序

归并排序（MERGE-SORT）：该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。实现序列的完全有序，需要将已经有序的子序列合并，即先让每个子序列有序，然后再将相邻的子序列段有序。若将两个有序表合并成一个有序表，称为二路归并。

时间复杂度：O(n*logN)（无论有序还是无序）

空间复杂度：O（N）。是稳定的排序。

    //归并排序：递归
    public static void mergeSort(int[] array,int left,int right){
        if(left>=right){
            return;
        }
        int mid=(left+right)/2;
        //递归分割
        mergeSort(array,left,mid);
        mergeSort(array,mid+1,right);
        //合并
        merge(array,left,right，mid);
    }
    //非递归
    public static void mergeSort1(int[] array){
        int gap=1;
        while(gap<array.length){
            for (int i = 0; i < array.length; i+=2*gap) {
                int left=i;
                int mid=left+gap-1;
                if(mid>=array.length){
                    mid=array.length-1;
                }
                int right=left+2*gap-1;
                if(right>=array.length){
                    right=array.length-1;
                }
                merge(array,left,right,mid);
            }
            gap=gap*2;
        }
    } 
    //合并：合并两个有序数组
    public static void merge(int[] array,int left,int right，int mid){
        int[] tmp=new int[right-left+1];
        int k=0;
        int s1=left;
        int e1=mid;
        int s2=mid+1;
        int e2=right;
        while(s1<=e1&&s2<=e2){
            if(array[s1]<=array[s2]){
                tmp[k++]=array[s1++];
            }else{
                tmp[k++]=array[s2++];
            }
        }
        while(s1<=e1){
            tmp[k++]=array[s1++];
        }
        while(s2<=e2){
            tmp[k++]=array[s2++];
        }
        for (int i = left; i <= right; i++) {
            array[i]=tmp[i-left];
        }
    }

五、排序算法的分析

排序方法	最好时间复杂度	最坏时间复杂度	空间复杂度	稳定性
直接插入排序	O(n)	O(n^2)	O(1)	稳定
希尔排序	O(n)	O(n^2)	O(1）	不稳定
直接排序	O(n^2)	O(n^2)	O(1)	不稳定
堆排序	O(nlog(2)n)	O(nlog(2)n)	O(1)	不稳定
冒泡排序	O(n)	O(n^2)	O(1)	稳定
快速排序	O(nlog(2)n)	O(n^2)	O(nlog(2)n)	不稳定
归并排序	O(nlog(2)n)	O(nlog(2)n)	O(n)	稳定

The above is the detailed content of How to use the seven sorting methods of Java data structures. For more information, please follow other related articles on the PHP Chinese website!