纯碎coding：7个最常用的排序算法

1    //swap element at i to at j
2    private static void swap(int[] array, int i,int j){
3       int tmp = array[i];
4       array[i] = array[j];
5       array[j] = tmp;
6    }

 1    //bubble sort
 2     public static void bubbleSort(int[] array, int n){
 3        int i = 0;// loop
 4        int j = 0; // element index
 5        while(i < n) {
 6           for(j=0; j<n-i-1; j++){
 7              if( array[j] > array[j+1] ){ //swap condition
 8                 swap( array, j, j +1 );
 9               }
10           }
11           i++;
12        }
13     }

 1    //quick sort
 2    public static void quickSort(int[] array, int lo, int hi){
 3        if(lo>hi) return;
 4        int pivot = array[lo]; 
 5        int i = lo;
 6        int j = hi;
 7        while( i<j ){
 8            //get smaller after pivot 
 9            //warning: while condition, here and next while
10            //at least one item is >=
11            while(i < j && array[j] >= pivot){
12                j--;
13            }
14            array[i] = array[j]; //so at j an element is void
15            //get bigger before pivot
16            while(i < j && array[i] < pivot){
17                i++;
18            }
19            array[j] = array[i]; // at i an element is to fill at j
20        }
21       //here, i bumps into j
22        array[i] = pivot;
23        //here, before index i smaller than pivot, after bigger than pivot
24        // lo~i quick sort
25        quickSort(array, lo, i-1);  
26        // i+1~hi quick sort
27        quickSort(array, i+1, hi); 
28     }

 1     //direct select sort
 2    public static void selectSort(int[] array, int n){
 3        int i=0; //sorted last element
 4        int j=0; //unsorted first element
 5        while(i<n){
 6            int min=array[i];
 7            int index = i;
 8            for(j=i+1; j<n;j++){
 9                if(array[j]<min){
10                    min = array[j];
11                    index = j;
12                }
13            }
14            swap(array,i,index);
15            i++;
16        }
17    }

 1 //heap sort
 2        public static void heapSort(int[] array, int n){    
 3            for (int i = n / 2 - 1; i >= 0; i--)
 4                buildHeap(array, n, i);
 5            int len = n - 1;
 6            while (len > 0) {           
 7                swap(array, 0, len);
 8                buildHeap(array, len, 0);
 9                len--;
10            }
11        }
12
13        private static void buildHeap(int[] array, int n, int i){
14            for (; left(i) < n; i = left(i)) {
15                int bigger =
16                    right(i) < n ? max(array, left(i), right(i)) : left(i);
17                if (array[bigger] > array[i]) //swap
18                    swap(array, bigger, i);
19                else break;
20            }
21        }
22
23    private static int left(int i){
24        return 2*i+1;
25    }
26
27    private static int right(int i){
28     return 2*i+2;
29
30    }
31
32    private static int max(int[] array, int i, int j){
33        return array[i]>array[j]? i:j;
34
35    }

 1     // insert sort
 2    public static void insertSort(int[] array, int n){
 3       int i = 1; //unsorted first index
 4       while (i < n) {
 5        int j = i - 1; //sorted last index
 6        int insert = array[i]; //warning: label array[i]
 7        while (j > 0 && insert < array[j]){                
 8            array[j + 1] = array[j];
 9            j--;
10         }               
11        array[j + 1] = insert; //j+1 is insert pos
12        i++;
13       }
14    }

 1    //shell Sort
 2     public static void shellSort(int[] array, int n, int group){
 3        if (group > n) return;
 4        int d = n / group; //d: number for each group
 5        while (d > 0){
 6           for (int i = 0; i < d; i++){
 7                 int j = i; // number index
 8                 int k = 1; //distance index
 9                 while (j < n){
10                        int insert = array[j]; //label unsorted first
11                        j -= d; //sorted last index
12                        while (j > 0 && insert < array[j]){
13                            array[j + d] = array[j];
14                            j -= d;
15                        }
16                   array[j + d] = insert; //insert pos: j+d
17                   j = i + (++k) * d; //next number index
18                }
19           }
20          d /= 2;
21        }
22     }   

 1 //merge sort
 2public static void mergeSort(int[] array, int n){
 3            var sorted = new int[n];
 4            mergeSort(array,sorted,0,n-1);
 5  }
 6
 7 private static void mergeSort(int[] array, int[] sorted, int lo, int hi){
 8            if (lo < hi){
 9                int mid = lo + (hi - lo) / 2;
10                mergeSort(array, sorted,lo, mid);
11                mergeSort(array, sorted, mid + 1, hi);
12                merge(array, sorted, lo, mid, hi);
13            }
14
15   }
16
17        //beg: part1 beginning index
18        //mid: part1 end index
19        //mid+1: part2 beginning index
20        //end: part2 end index
21
22   private static void merge(int[] array, int[] sorted, int beg, int mid, int end){
23            int i = beg; //part1 index
24            int j = mid + 1; //part2 index
25            int k = 0; //merged index
26            while (i <= mid && j <= end)
27                sorted[k++] = 
28                    array[i] <= array[j] ? array[i++] : array[j++];                
29            while (i <= mid)
30               sorted[k++] = array[i++];
31           while (j <= end)
32                sorted[k++] = array[j++];
33            for (i = 0; i < k; i++)
34                array[beg + i] = sorted[i]; 
35     }