基本排序算法代码实现，以及使用场景推荐

 1     // 冒泡排序
 2     public static void Bubble_Sort(int[] A, int n){
 3         int flag = 0;
 4         // 进行 n - 1 轮冒泡
 5         for(int i = n - 1; i > 0; i--){
 6             flag = 0;
 7             for(int j = 0; j < i; j++){
 8                 if(A[j] > A[j + 1]){
 9                     // 交换 A[j] 和 A[j + 1]
10                    A[j] ^= A[j + 1];
11                    A[j + 1] ^= A[j];
12                    A[j] ^= A[j + 1];
13                    flag = 1;
14                 }
15             }
16             if(flag == 0)   // 此轮没发生交换，排序结束
17                 break;
18         }
19     }

 1 // 插入排序
 2 public static void Insertion_Sort(int[] A, int n){
 3     int temp, i, j;
 4     for(i = 1; i < n; i++){
 5         temp = A[i];
 6         for(j = i; j > 0 && A[j - 1] > temp; j--){
 7             A[j] = A[j - 1];
 8         }
 9         A[j] = temp;
10     }
11 }

 1 // 希尔排序， 最坏情况 为 O(n^2)
 2 static void Shell_Sort(int A[], int n){
 3     int d,i, j, temp;     // d 为增量
 4     for(d = n / 2; d > 0; d /= 2){
 5         // 内部是一个增量为 d 的插入排序
 6         for(i = d; i < n; i++){
 7             temp = A[i];
 8             for(j = i; j >= d && A[j - d] > temp; j -= d)
 9                 A[j] = A[j - d];
10             A[j] = temp;
11         }
12     }
13 }

 1 // 堆排序
 2 public static void downAdjust(int[] A, int p, int n){
 3     int parent, child = p;
 4     int x = A[p];           // 取出根节点的值
 5     for(parent = p; (2 * parent + 1) < n; parent = child){
 6         child = 2 * parent + 1;
 7         // 如果右孩子存在且比左孩子大
 8         if(child + 1 < n && A[child + 1] > A[child]){
 9             child++;
10         }
11         if(x >= A[child])        // 与最大孩子结点比较, 如果父节点大，说明找到了位置
12             break;
13         else
14             A[parent] = A[child];   // 否则让最大孩子上位
15     }
16     A[parent] = x;      // 退出循环说明找到了 p 的位置
17 }
18 
19 public static void Heap_Sort(int[] A, int n){
20     // 建立最大堆
21     for(int i = n / 2 - 1; i >= 0; i--){ // 从第一个右孩子的结点向下调整
22         downAdjust(A, i, n);
23     }
24     for(int i = n - 1; i > 0; i--){
25         // 将堆顶元素与当前未排序的最后一个元素交换
26         int temp = A[i];
27         A[i] = A[0];
28         A[0] = temp;
29         downAdjust(arr, 0, i);
30     }
31 }

 1 // 选择排序， 最坏情况为 O(n^2), 不稳定 如 2 2 3 4 5 1
 2 public static void Selection_Sort(int[] A, int n){
 3     int k, temp;
 4     for(int i = 0; i < n - 1; i++){
 5         k = i;
 6         for(int j = i + 1; j < n; j++){
 7             if(A[j] < A[k])
 8                 k = j;      // 找到最小的元素的下标
 9         }
10         temp = A[k];
11         A[k] = A[i];
12         A[i] = temp;
13     }
14 }

 1 public static void Merge(int[] A, int[] temp, int LL, int LR, int RL, int RR){
 2     int left = LL;
 3     int index = LL;
 4     while(LL <= LR && RL <= RR) {
 5         if (A[LL] <= A[RL]) {
 6             temp[index++] = A[LL++];
 7         } else {
 8             temp[index++] = A[RL++];
 9         }
10     }
11     while(LL <= LR)
12         temp[index++] = A[LL++];
13     while(RL <= RR)
14         temp[index++] = A[RL++];
15 
16     // 将temp元素 复制到 A 数组中
17     for(int i = left; i < index; i++)
18         A[i] = temp[i];
19 
20 }
21 
22 public static void Msort(int[] A, int temp[], int left, int right){
23     int center;
24     if(left < right){
25         center = (right + left) / 2;
26         Msort(A, temp, left, center);       // 归并做半段元素
27         Msort(A, temp, center + 1, right);  // 归并y右半段元素
28         Merge(A, temp, left, center, center + 1, right);    // 合并左右两段
29     }
30 }
31 
32 // 归并排序 递归方式 复杂度为 O(nlogn)
33 public static void MergeSort(int[] A, int n){
34     int[] temp = new int[1000];         // 借助一个辅助富足，每次将两段区间排好序的元素存在temp数组总
35     Msort(A, temp, 0, n - 1);
36 }

 1 // 随机选取主元，对区间 [left, right] 进行划分
 2 public static int randPartition(int[] A, int left, int right){
 3     // 生成一个 [left, right] 范围内的随机数, 随机让排序平均复杂度更低
 4     Random r = new Random();
 5     int p = r.nextInt(right - left) + left;
 6 
 7     int temp = A[left];
 8     A[left] = A[p];
 9     A[p] = temp;
10 
11     int pivot = A[left];
12     while(left < right){    // 只要 left 与 right 不相遇
13         while(left < right && A[right] > pivot)
14             right--;
15         A[left] = A[right];
16         while(left < right && A[left] <= pivot)
17             left++;
18         A[right] = A[left];
19     }
20     A[left] = pivot;
21     return left;
22 }
23 
24 // 快速排序， left 与 right 初值为序列首尾下标
25 public static void quickSortHelp(int[] A, int left, int right){
26     if(left < right){   // 当区间长度超过 1 时
27         // 将 [left, right] 按照 A[left] 为主元，一分为二
28         int pos = randPartition(A, left, right);
29         quickSortHelp(A, left, pos - 1);
30         quickSortHelp(A, pos + 1, right);
31     }
32 }
33 
34 public static void quickSort(int[] A, int n){
35     quickSortHelp(A, 0, n - 1);
36 }