1. 选择排序（Selection Sort）

基本思想：

首先找到数组中最小的那个元素，将它和数组的第一个元素交换位置。然后在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序

算法分析：

时间复杂度： O ( n 2 ) O(n^2) O(n2)

空间复杂度： O ( 1 ) O(1) O(1)

稳定性：不稳定排序

public class SelectIonSort {
    public SelectIonSort() {
    }
    public static void main(String[] args) {
        int[] arr = new int[]{1, 3, 6, 8, 78, 9, 48, 8, 56};
        selectionSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    public static void selectionSort(int[] arr) {
        for(int i = 0; i < arr.length - 1; ++i) {
            int min_index = i;
            for(int j = i + 1; j < arr.length; ++j) {
                if (arr[j] < arr[min_index]) {
                    min_index = j;
                }
                swap(arr, i, min_index);
            }
        }
    }
}

2. 直接插入排序（Insertion Sort）

基本思想：

把第一个元素作为有序部分，从第二个元素开始将剩余元素逐个插入有序部分的合适位置，最终得到排序的序列。

算法分析：

时间复杂度： O ( n 2 ) O(n^2) O(n2)

空间复杂度： O ( 1 ) O(1) O(1)

稳定性：稳定排序

public class InsertSort {

    public static void main(String[] args) {
        int[] arr = new int[]{1, 3, 6, 8, 78, 9, 48, 8, 56};
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    public static void insertSort(int[] arr) {
        for(int i = 1; i < arr.length; ++i) {
            for(int j = i; j > 0 && arr[j] < arr[j - 1]; --j) {
                swap(arr, j, j - 1);
            }
        }
    }
}

3. 冒泡排序（Bubble Sort）

基本思想：

把第一个元素与第二个元素比较，如果第一个比第二个大，则交换他们的位置。接着继续比较第二个与第三个元素，如果第二个比第三个大，则交换他们的位置……对每一对相邻元素执行同样操作，一趟比较完成后，排在最右的元素便是最大的数。除去最右的元素，对剩余的元素做同样的工作，最终得到排序序列

算法分析：

时间复杂度： O ( n 2 ) O(n^2) O(n2)

空间复杂度： O ( 1 ) O(1) O(1)

稳定性：稳定排序

public class BubbleSort {
    public static void bubbleSort(int[] array) {
        for(int i = 0; i < array.length - 1; ++i) {
            for(int j = 0; j < array.length - 1 - i; ++j) {
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;   }}}    
                    } 
    public static void main(String[] args) {
        int[] arr = new int[]{1, 6, 2, 2, 5};
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

4. 希尔排序（Shell Sort）

基本思想：

希尔排序可以说是插入排序的一种变种。无论是插入排序还是冒泡排序，如果数组的最大值刚好是在第一位，要将它挪到正确的位置就需要 n - 1 次移动。也就是说，原数组的一个元素如果距离它正确的位置很远的话，则需要与相邻元素交换很多次才能到达正确的位置，这样是相对比较花时间了。

希尔排序就是为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序。先让数组中任意间隔为 h 的元素有序，刚开始 h 的大小可以是 h = n / 2,接着让 h = n / 4，让 h 一直缩小，当 h = 1 时，也就是此时数组中任意间隔为1的元素有序，此时的数组就是有序的了。

算法分析：

时间复杂度： O ( n 2 ) O(n^2) O(n2)

空间复杂度： O ( 1 ) O(1) O(1)

稳定性：不稳定排序

public class ShellSort {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 3, 6, 8, 78, 9, 48, 8, 56};
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    public static void shellSort(int[] arr) {
        for(int gap = arr.length / 2; gap > 0; gap /= 2) {
            for(int i = gap; i < arr.length; ++i) {
                for(int j = i; j >= gap && arr[j] < arr[j - gap]; j -= gap) {
                    swap(arr, j, j - gap);
                }
            }
        }
    }
}

5. 归并排序（Merge Sort）

基本思想：

归并排序是建立在归并操作上的一种有效的排序算法。该算法是分治法（Divide and Conquer）的典型应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

根据具体的实现，归并排序包括"从上往下"和"从下往上"2种方式。

从下往上（循环）：将待排序的数列分成若干个长度为1的子数列，然后将这些数列两两合并；得到若干个长度为2的有序数列，再将这些数列两两合并；得到若干个长度为4的有序数列，再将它们两两合并；直到合并成一个数列为止。这样就得到了最终的排序结果。

从上往下（递归）：它基本包括3步：

分解：将当前区间一分为二，即求分裂点 mid = (low + high) / 2； 求解：递归地对两个子区间 [low…mid] 和 [mid+1…high] 进行归并排序。递归的终结条件是子区间长度为1； 合并：将已排序的两个子区间 [low…mid] 和 [mid+1…high] 归并为一个有序的区间 [low…high]

算法分析：

时间复杂度： O ( n ∗ l o g n ) O(n*logn) O(n∗logn)

空间复杂度： O ( n ) O(n) O(n)

稳定性：稳定排序

public class MergeSort {
    public static void main(String[] args) {
        int[] array = new int[]{1, 3, 6, 8, 78, 9, 48, 8, 56};
        mergeSort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));
    }
    public static void mergeSort(int[] array, int low, int height) {
        if (low < height) {
            int mid = low + height >>> 1;
            mergeSort(array, low, mid);
            mergeSort(array, mid + 1, height);
            merge(array, low, mid, height);
        }
    }
    public static void merge(int[] array, int low, int mid, int height) {
        int s1 = low;
        int s2 = mid + 1;
        int[] ret = new int[height - low + 1];
        int var7 = 0;
        while(s1 <= mid && s2 <= height) {
            if (array[s1] <= array[s2]) {
                ret[var7++] = array[s1++];
            } else {
                ret[var7++] = array[s2++];
            }
        }
        while(s1 <= mid) {
            ret[var7++] = array[s1++];
        }
        while(s2 <= height) {
            ret[var7++] = array[s2++];
        }
        for(int j = 0; j < ret.length; ++j) {
            array[j + low] = ret[j];
        }
    }
}

6. 快速排序（Quick Sort）

基本思想：

从数组中选择一个元素，称为中轴元素。把数组中所有小于中轴元素的元素放在其左边，所有大于或等于中轴元素的元素放在其右边，显然，此时中轴元素所处的位置的是有序的。也就是说，我们无需再移动中轴元素的位置。

以中轴元素为界把大的数组切割成两个小的数组（分割操作，partition），且两个数组都不包含中轴元素。对中轴元素左右两边的数组进行递归操作，直到数组的大小为1。此时每个元素都处于有序的位置。

算法分析：

时间复杂度： O ( n ∗ l o g n ) O(n*logn) O(n∗logn)

空间复杂度： O ( l o g n ) O(logn) O(logn)

稳定性：不稳定排序

public class QuickSort {
    public static void quickSort(int[] arrays, int left, int right) {
        if (left <= right) {
            int l = left;
            int r = right;
            int pivot = arrays[left];
            boolean var6 = false;
            while(l < r) {
                while(pivot <= arrays[r] && l < r) {
                    --r;
                }
                while(pivot >= arrays[l] && l < r) {
                    ++l;
                }
                if (l <= r) {
                    int temp = arrays[r];
                    arrays[r] = arrays[l];
                    arrays[l] = temp;
                }
            }
            arrays[left] = arrays[l];
            arrays[l] = pivot;
            quickSort(arrays, left, l - 1);
            quickSort(arrays, l + 1, right);
        }
    }
    public static void main(String[] args) {
        int[] arr = new int[]{1, 3, 6, 8, 78, 9, 48, 8, 56};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}

7. 堆排序（Heap Sort）

基本思想：

堆的特点就是堆顶的元素是一个最值，大顶堆的堆顶是最大值，小顶堆则是最小值。

堆排序就是把堆顶的元素与最后一个元素交换，交换之后破坏了堆的特性，我们再把堆中剩余的元素再次构成一个大顶堆，然后再把堆顶元素与最后第二个元素交换….如此往复下去，等到剩余的元素只有一个的时候，此时的数组就是有序的了。

算法分析：

时间复杂度： O ( n ∗ l o g n ) O(n*logn) O(n∗logn)

空间复杂度： O ( 1 ) O(1) O(1)

稳定性：不稳定排序

public class HeapSort {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 3, 6, 8, 78, 9, 48, 8, 56};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void heapSort(int[] arr) {
        int i;
        for(i = arr.length / 2 - 1; i >= 0; --i) {
            heapify(arr, i, arr.length - 1);  }  
        for(i = arr.length - 1; i > 0; --i) {
            swap(arr, 0, i);
            heapify(arr, 0, i - 1);    }
        }
    public static void heapify(int[] arr, int i, int last_index) {
        int max = i;
        if (2 * i + 1 <= last_index) {
            max = 2 * i + 1;       } 
        if (2 * i + 2 <= last_index && arr[2 * i + 2] > arr[max]) {
            max = 2 * i + 2;     }   
        if (max != i) {
            swap(arr, i, max);
            heapify(arr, max, last_index);      }    } 
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

8. 计数排序（Counting Sort）

基本思想：

计数排序适合于最大值和最小值的差值不是很大的情况。

把数组元素作为数组的下标，然后用一个临时数组统计该元素出现的次数，例如 temp[i] = m, 表示元素 i 一共出现了 m 次。最后再把临时数组统计的数据从小到大汇总起来，此时汇总起来是数据是有序的。

算法分析：

时间复杂度： O ( n + k ) O(n+k) O(n+k)，其中k为临时数组大小

空间复杂度： O ( k ) O(k) O(k)

稳定性：稳定排序

public class CountSort {
    public static void countSort(int[] arr) {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        int[] count = new int[max + 1];
        for (int i = 0; i < arr.length; i++) {
            count[arr[i]]++;
        }
        int k = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                arr[k++] = i;
                count[i]--;
            }
        }
    }
    public static void main(String[] args) {
        int[] arr = new int[]{1, 3, 6, 8, 78, 9, 48, 8, 56};
        CountSort.countSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

9. 桶排序（Bucket Sort）

基本思想：

桶排序就是把最大值和最小值之间的数进行瓜分，例如分成 10 个区间，10个区间对应10个桶，我们把各元素放到对应区间的桶中去，再对每个桶中的数进行排序，可以采用归并排序、快速排序等方法。之后每个桶里面的数据就是有序的了，按顺序遍历各桶即可得到排序序列。桶排序也可用于浮点数排序。

算法分析：

时间复杂度： O ( n + k ) O(n+k) O(n+k)

空间复杂度： O ( k ) O(k) O(k)

稳定性：稳定排序

public class BucketSort {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 3, 6, 8, 78, 9, 48, 8, 56};
        CountSort.countSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void bucketSort(int[] arr) {
        int max = arr[0];
        int min;
        for(min = 1; min < arr.length; ++min) {
            if (arr[min] > max) {
                max = arr[min];
            }
        }
        min = arr[0];
        for(int i = 1; i < arr.length; ++i) {
            if (arr[i] < min) {
                min = arr[i];
            }
        }
        ArrayList<ArrayList<Integer>> buckets = new ArrayList();
        int count = (max - min) / arr.length + 1;

        int k;
        for(k = 0; k < count; ++k) {
            buckets.add(new ArrayList());
        }
        for(k = 0; k < arr.length; ++k) {
            ((ArrayList)buckets.get((arr[k] - min) / arr.length)).add(arr[k]);
        }
        for(k = 0; k < buckets.size(); ++k) {
            Collections.sort((List)buckets.get(k));
        }
        k = 0;
        for(int i = 0; i < buckets.size(); ++i) {
            ArrayList<Integer> list = (ArrayList)buckets.get(i);
            for(int j = 0; j < list.size(); ++j) {
                arr[k++] = (Integer)list.get(j);
            }
        }
    }
}

10. 基数排序（Radix Sort）

基本思想：

先以个位数的大小来对数据进行排序，接着以十位数的大小来多数进行排序，接着以百位数的大小……

排到最后，就是一组有序的元素了。在以某位数进行排序的时候，是用“桶”来排序的。

由于某位数（个位/十位….，不是一整个数）的大小范围为0~9，所以我们需要10个桶，然后把具有相同数值的数放进同一个桶里，之后再把桶里的数按照0号桶到9号桶的顺序取出来。一趟下来按照某位数的排序就完成了。

算法分析

时间复杂度： O ( k ∗ n ) O(k*n) O(k∗n)

空间复杂度： O ( k + n ) O(k+n) O(k+n)

稳定性：稳定排序

public class RadixSort {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 322, 68, 8, 78, 9, 48, 8, 569, 999, 148, 56};
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void radixSort(int[] arr) {
        int max = arr[0];
        int exp;
        for(exp = 1; exp < arr.length; ++exp) {
            if (arr[exp] > max) {
                max = arr[exp]; }
           
        }
        for(exp = 1; max / exp > 0; exp *= 10) {
            int[] buckets = new int[10];
            int[] temp = new int[arr.length];
            int i;
            for(i = 0; i < arr.length; ++i) {
                ++buckets[arr[i] / exp % 10];
            }
            for(i = 1; i < buckets.length; ++i) {
                buckets[i] += buckets[i - 1];
            }
            for(i = arr.length - 1; i >= 0; --i) {
                temp[buckets[arr[i] / exp % 10] - 1] = arr[i];
                --buckets[arr[i] / exp % 10];
            }
            for(i = 0; i < temp.length; ++i) {
                arr[i] = temp[i];
            }
        }
    }
}