当前位置:网站首页>Data structure and sorting algorithm

Data structure and sorting algorithm

2020-11-07 21:19:25 Long Tao

Sorting algorithm :

  1. Internal sorting : It refers to loading all the data to be processed into internal memory for sorting

  2. External sorting : When the amount of data is too large , Can't load all into memory , Sorting needs to be done with the help of external memory

  3. Common algorithm classification :


5.1 Bubble sort

The basic idea : By treating sort Before and after ( Start with elements with small subscripts ), Compare the values of adjacent elements in turn , If it is found that the reverse order is found, it will be exchanged , Gradually move the higher value elements from the front to the back , It's like a start at the bottom of the water .

Summary rules :

  1. A total of n-1 A large cycle ( Array has n Elements )
  2. The elements of each sort are gradually decreasing
  3. If in the process of sorting , There was no exchange , It shows that the sorting has been completed
public static int[] bubbleSort(int[] arr) {
        int temp = 0;
        boolean flag = false;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if(arr[j] > arr[j+1]){
                    flag = true;
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }

            if(!flag){
                break;
            }else {
                flag = false;
            }
        }
        return arr;
    }

5.2 Selection sort

Selection sort is also an internal sort , It is to select an element from the data to be sorted according to specified rules , Then according to the rules of exchange position to achieve the purpose of sorting .

The idea of sorting :

  1. from arr[0]--arr[n-1] Find the smallest number in , Then exchange arr[0] Swap positions with the minimum
  2. from arr[1]--arr[n-1] Find the smallest number in , Then exchange arr[1] Swap positions with the minimum
  3. ........
  4. Until all the data is exchanged
//  Selection sort , Select the smallest element in the array with arr[0] swapping , Then continue to look for the next minimum and arr[1] In exchange for , Until all the data is sorted 
public static int[] selectSort(int[] arr){
        int temp = 0;
        int index = 0;
        for (int i = 0; i < arr.length-1; i++) {
            index = i;	//  The index of the initial minimum value is i
            for (int j = i+1; j < arr.length; j++) {
                 // If arr[j] Less than arr[index], be j Is the index of the minimum value 
                if(arr[j] < arr[index]){	
                    index = j;
                }
            }
            //  Exchange the minimum and arr[i] The location of 
            temp = arr[i];
            arr[i] = arr[index];
            arr[index] = temp;
        }

        return arr;
    }

5.3 Insertion sort

Insertion sort belongs to internal sort method , It is to find the appropriate position of the element to be sorted by inserting .

Insert the idea of sorting : hold n Elements to be sorted Think of it as an ordered table and an unordered table , At first, the ordered table contains only one element , The unordered table contains n-1 Elements . In the process of sorting , Take the first element from the unordered table every time , Insert it in place in an ordered list , Make it a new ordered list .

Code implementation :

/**
     *  Insertion sort , Think of a list as an ordered table and an unordered table 
     * @param arr
     * @return
     */
public static int[] insertSort(int[] arr){
    int temp = 0;
    int index = 0;
    for (int i = 1; i < arr.length; i++) {
        temp = arr[i];
        index = i-1;
        //  Flashback judgment from i-1 To 0 Judge , If appear temp>arr[index], shows arr[index+1] The part to be inserted 
        while (index >= 0  && temp < arr[index]){
            arr[index+1] = arr[index];	// Move the data in turn 
            index --;
        }
        //  stay arr[index+1] Insert data 
        arr[index+1] = temp;
    }

    return arr;
}

5.4 Shell Sort ( Reduced delta sort )

The basic idea : Hill sort is to group records by a certain increment of subscript , Sort each group using the direct insertion sort algorithm ; As the increments decrease , Each group contains more and more keywords , When the increment is reduced to 1 when , The whole document is just a group , The algorithm terminates .

Step by step , Divide a certain amount of data into groups . Settings for each group The data increment is half of the last increment , Then increase the amount of data in each group , Array reduction , Until there's only one array left .

Hill sort method :

  1. When inserting an ordered sequence, we use Exchange method
  2. When inserting an ordered sequence, we use Mobile method
 /**
     *  Hill exchange 
     * @param arr
     * @return
     */
    public static int[] shellSort(int[] arr){
        int temp = 0;
        int count = 0;
        for(int gap = arr.length/2; gap > 0; gap /= 2){
            for(int i=gap; i< arr.length; i++){
                //  Traverse all the data in the group ,gap Step length 
                for(int j=i-gap; j >= 0; j -= gap){
                    if(arr[j] > arr[j+gap]){
                        temp = arr[j];
                        arr[j] = arr[j+gap];
                        arr[j+gap] = temp;
                    }
                }
            }
        }

        return arr;
    }

//  Mobile location ( Combined with insertion sort )
    public static int[] shellMoveSort(int[] arr){
        for(int gap = arr.length/2; gap > 0; gap /= 2){
            for(int i=gap; i < arr.length; i++){
                int j = i;
                int temp = arr[j];
                if(arr[j] < arr[j-gap]){
                    while (j - gap >= 0 && temp < arr[j - gap]){
                        arr[j] = arr[j-gap];
                        j -= gap;
                    }

                    arr[j] = temp;
                }
            }
        }
        return arr;
    }

5.5 Quick sort

The basic idea : Divide the data to be sorted into Two separate parts , All the data in one part is more than all the data in the other part All have to be small. , Then, the data distribution of the two parts is sorted in this way , The whole sorting part can be done recursively , So that the whole data becomes an ordered sequence .

img

Thought analysis :

  1. Let's say the array is arr, On the left left, The right side is right, Set the initial position of the selection to
  2. Find from left , Find greater than or equal to mid The value of , Start on the right side, too , Until we find less than or equal to mid Value
  3. Until I find l<r The location of , And then recursively do a quick sort .
/**
     *  Quick sort 
     *
     * @param arr
     * @param left
     * @param right
     * @return
     */
public static int[] quickSort(int[] arr, int left, int right) {
    if (left >= right) return null;
    //  If the left And right Equal or left Greater than right, Then jump out of the program 
    int l = left;
    int r = right;
    int mid = arr[(l + r) / 2];
    int temp = 0;
    while (l < r) {
        while (l < r && arr[l] < mid) {
            l++;
        }

        while (r > l && arr[r] > mid) {
            r--;
        }

        if (l >= r) {
            break;
        }

        temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;

        if (arr[l] == mid){
            r--;
        }
        if (arr[r] == mid) {
            l++;
        }
    }

    quickSort(arr, left, l - 1);
    quickSort(arr, r + 1, right);
    return arr;
}

5.6 Merge sort

Merge sort is a sort method realized by using the idea of merging , The algorithm uses the classic Divide and conquer strategy ( Divide and conquer will make the problem branch For some small problems and then recursively solve them , and Governance stage Then we will get the answers in different stages “ repair ” together , namely Divide and rule

The basic method :

  1. First, the array is divided into two parts , Split until there is only one element in each subarray
  2. Then merge the same adjacent split parts , Merge in order , Until it's merged into a complete array
  3. It's best to do it recursively , The time complexity is O(nlogn)

img

 /**
     *  Merge sort 
     * @param arr
     * @param left
     * @param right
     * @return
     */
public static int[] mergeSort(int[] arr, int left, int right){
    //  If left Greater than right, Only... In the array 1 Or no data , Then it will return empty directly 
    if(left >= right) return null;
    int mid = (left + right)/2;

    //  Division 
    mergeSort(arr, left, mid);
    mergeSort(arr, mid+1, right);

    int i = left;
    int j = mid+1;
    int t = 0;
    int[] temp = new int[(right - left + 1)];
    while (i <= mid && j <= right){
        if(arr[i] <= arr[j]){
            temp[t] = arr[i];
            t ++;
            i ++;
        }else {
            temp[t] = arr[j];
            t ++;
            j ++;
        }
    }
    //  Fill in the rest with temp in 
    while (i <= mid){
        temp[t] = arr[i];
        t++;
        i++;
    }
    //  Put the rest right Fill in the content with temp in 
    while (j <= right){
        temp[t] = arr[j];
        t++;
        j++;
    }

    //  take temp Copy the data to arr in 
    for(int k=left; k<=right; k++){
        arr[k] = temp[k-left];
    }
    System.out.println(" The sorted data is :" + Arrays.toString(temp));
    return arr;
}

5.7 Radix sorting

  1. Cardinal sort belongs to “ Distributive sort ”, also called Barrel method , It is through the value of each bit of the key value , Assign the elements to be sorted to some “ bucket ” in , To achieve the function of sorting
  2. Cardinal sort belongs to stable sort , Cardinality sorting is a stable sorting method with high efficiency
  3. Cardinal sort is Bucket sort Development of
  4. The implementation of cardinality sort : Cut the whole number into different numbers according to the number of digits , And then compare... According to each bit .

img

Method of implementation :

  1. Define a two-dimensional array , Express 10 A barrel , Every bucket is a one-dimensional array
  2. In order to prevent data overflow when putting in input , Then every one-dimensional array ( bucket ), Size to arr.length
  3. Cardinal sort is a classical algorithm that uses space for time .
 /**
     *  Radix sorting 
     * @param arr
     * @return
     */
public static int[] radixSort(int[] arr){
    int[][] bubble = new int[10][arr.length];   // Set the number of barrels , Each bucket holds the entire array at most 
	//  Find the largest number in the array 
    int max = arr[0];
    for(int i=1; i<arr.length; i++){
        if(arr[i] > max){
            max = arr[i];
        }
    }

    int maxLength = (max + "").length();
    //  Determine how many cycles are required based on the number of digits of the largest data in the value 
    for (int i = 0; i < maxLength; i++) {
        int[] bubbleLength = new int[10];   //  The amount of data in the bucket 
        //  Put the data according to bits 、 ten 、 Put the hundred in the bucket in turn 
        for (int j = 0; j < arr.length; j++) {
            int size = arr[j] / (int)Math.pow(10, i) % 10;
            bubble[size][bubbleLength[size]] = arr[j];
            bubbleLength[size] ++;
        }

        // Take the data out in turn , And put it into the original array 
        int index = 0;
        for(int j=0; j<bubble.length; j++){
            if(bubbleLength[j] > 0){
                for(int k=0; k<bubbleLength[j]; k++){
                    arr[index++] = bubble[j][k];
                }
            }
        }
    }

    return arr;
}

版权声明
本文为[Long Tao]所创,转载请带上原文链接,感谢