当前位置：网站首页>Quick sort + bubble sort + insert sort + select sort

Quick sort + bubble sort + insert sort + select sort

2022-06-23 07:43:00 【Donkey of the production team】

Code

Selection sort

public class Solution {
    
    /** * @param a: an integer array * @return: nothing */
    public void sortIntegers(int[] a) {
    
        // write your code here

        int n = a.length;

        for (int i = 0; i < n - 1; i++){
    
            int min = i;
            for (int j = i + 1; j < n; j++){
    
                if (a[j] < a[min]){
    
                    min = j;
                }
            }
            swap(a, i, min);
        }
    }
     public void swap(int[] a, int index1, int index2){
    
         int temp = a[index1];
         a[index1] = a[index2];
         a[index2] = temp;
     }
}

Bubble sort

// bubble sort
 public class Solution{
    
     public void sortIntegers(int[] a){
    
         int n = a.length;

        for (int i = 0; i < n- 1;i++){
    
             for (int j = 0; j < n - 1 - i; j++){
    
              if (a[j] > a[j+1]) swap(a, j, j+1);
             }
         }
     }

     public void swap(int[] a, int index1, int index2){
    
         int temp = a[index1];
         a[index1] = a[index2];
         a[index2] = temp;
     }
 }

Quick sort

public class Solution{
    
    public void sortIntegers(int[] a) {
    
        int low = 0;
        int hight = a.length - 1;
        quickSort(a, low, hight);
    }

    public void quickSort(int[] a, int low, int hight){
    
        
        if (low > hight) return;

        int left, right, pivot;
        
        left = low;
        right = hight;
        pivot = a[left];

        while(left < right){
    
            while(left < right && a[right] >= pivot) right--;

            if (left < right) a[left] = a[right];

            while(left < right && a[left] <= pivot) left++;

            if (left < right) a[right] = a[left];

            if (left == right) a[left] = pivot;
        }

        quickSort(a, low, right - 1);
        quickSort(a, right + 1, hight);
    }
}

Quick sort In the video Do watch the video , Don't look at the code , Look directly at the code Not easy to understand
Horse soldiers or something , It is not easy to understand , Look at this

Insertion sort

public class Solution{
    
    public void sortIntegers(int[] a){
    
        int n = a.length;
        for (int i = 1; i < n; i++){
    
            int temp = a[i];
            int j = i;

            while (j > 0 && a[j - 1] > temp){
    
                a[j] = a[j - 1]; 
                j--;
            }

            a[j] = temp;
        }
    }
}