- 1. 冒泡排序(Bubble Sort)
- 初版冒泡排序
- 升级版：鸡尾酒冒泡排序
- 2. 选择排序(Selection Sort)
- 3. 插入排序(Insertion Sort)
- 4. 快速排序(Quick Sort)
- 单向寻找方式
- 双向寻找方式
- 5. 希尔排序(Shell Sort)
- 6. 归并排序
- 7. 堆排序
- 8. 基数排序
- 9. 桶排序
-
排序算法大体可分为两种：
- 一种是比较排序，时间复杂度O(nlogn) ~ O(n^2)，主要有： 冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。
- 另一种是非比较排序，时间复杂度可以达到O(n)，主要有： 计数排序，基数排序，桶排序等。
下面介绍常用的排序算法（升序排序）。
思路：对列表多次重复遍历，每相邻的两个数进行比较，大的往后移，就像冒泡一样，大的慢慢浮到后面去。
如下图：
所有代码使用到的swap函数：
public static void swap(int[] arr, int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
冒泡排序实现代码：
public static void bubbleSort(int[] arr){
int len = arr.length;
for (int i = 0; i < len; i++) {
for (int j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j+1]) {
swap(arr, j, j+1);
}
}
}
}
升级版：鸡尾酒冒泡排序
思路：遍历方式从低到高然后从高到低，从前到后再从后到前，先找最大的再找最小的。
public static void CocktailSort(int[] arr) {
int left = 0, len = arr.length; // 初始化边界
int right = len - 1;
while (left < right) {
// 前半轮,将最大元素放到后面
for (int i = left; i < right; i++) {
if (arr[i] > arr[i + 1]) {
swap(arr, i, i+1);//交换两个位置的数值
}
}
right--;
// 后半轮,将最小元素放到前面
for (int i = right; i > left; i--) {
if (arr[i - 1] > arr[i]) {
swap(arr, i, i-1);//交换两个位置的数值
}
}
left++;
}
}
2. 选择排序(Selection Sort)
思路：第一趟遍历完记录最小的数，放置到第一位（交换，当已在第一位时不交换）；继续遍历并记录剩余列表中的最小数，放置到第二位（交换）；以此类推。
使用下标记录当前最小值即可。
public static void selectionSort(int[] arr) {
int len = arr.length;
for (int i = 0; i < len - 1; i++) {
int idx = i; //记录最小值的下标
// 从 下标为i+1 往后寻找当前最小值的下标
for (int j = i + 1; j < len; j++) {
if (arr[idx] > arr[j]){
idx = j;
}
}
//找到了比arr[i]小的则与arr[i]交换位置
if (idx != i) {
swap(arr, i, idx); //交换两个位置的数值
}
}
}
3. 插入排序(Insertion Sort)
思路：元素被分为有序区和无序区两部分。最初有序区只有一个元素。每次从无序区中选择一个元素，插入到有序区的位置，直到无序区变空。
与抓扑克牌排序一样。摸第一张时认为已有序，摸第二张时插入到第一张的前或后进行排序，以此类推。
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
// 从当前i下标往前遍历，插入到相应的位置
for (int j = i; j > 0; j--) {
// 当前数比前面的数小，交换两数
if (arr[j] < arr[j-1]) {
swap(arr, j-1, j); //交换两个位置的数值
} else {
break;
}
}
}
}
// 插入排序之 右移 与 赋值
public static void insertionSort2(int[] arr) {
for (int i = 1; i < arr.length; i++) { // 类似抓扑克牌排序
int get = arr[i]; // 新抓一张牌
int j = i - 1; // 拿在手上的牌总是排序好的
while (j >= 0 && arr[j] > get) { // 将抓到的牌与手牌从右向左进行比较
arr[j + 1] = arr[j]; // 如果该手牌比抓到的牌大，就将其右移
j--;
}
arr[j + 1] = get; // 直到该手牌比抓到的牌小(或二者相等)，将抓到的牌插入到该手牌右边(相等元素的相对次序未变，所以插入排序是稳定的)
}
}
4. 快速排序(Quick Sort)
单向寻找方式
思路：
- 从序列中挑出一个元素，作为"基准"(pivot)。从下标为0开始。
- 把所有比基准值小的元素放在基准前面，所有比基准值大的元素放在基准的后面（相同的数可以到任一边），这个称为分区(partition)操作。
当基准值(pivot)取数组第0个，有x个比基准值小的，pivot最终的下标地址p_pos就为x。 - 对每个分区递归地进行步骤1~2，递归的结束条件是序列的大小是0或1，这时整体已经被排好序了。
public static void quickSort(int[] arr, int left, int right) {
int pivot; //基准
int p_pos; //存放基准下标地址：有x个比pivot小的数，p_pos就为x。
if (left < right) {
p_pos = left;
pivot = arr[p_pos]; //基准从数组的第0个开始取
// 从左往右遍历
for (int i = left + 1; i <= right; i++) {
// 当存在 第i个位置 < pivot，交换 p_pos+1 和 i 的数值
if (arr[i] < pivot){ // > 降序
p_pos++;
swap(arr, p_pos, i); //交换两个位置的数值
}
}
// 最终找到 pivot 该去的位置 p_pos，有x个比pivot小的数，p_pos就为x。
swap(arr, left, p_pos); //交换两个位置的数值
quickSort(arr, left, p_pos - 1);//递归当前基准 左边 的区域
quickSort(arr, p_pos + 1, right);//递归当前基准 右边 的区域
}
}
// 其他实现方式的快速排序
public static void _quickSort(int[] arr, int left, int right) {
if (left < right){
int pivot_index = partition(arr, left, right); // 基准的索引
_quickSort(arr, left, pivot_index - 1);
_quickSort(arr, pivot_index + 1, right);
}
}
public static int partition(int[] arr, int left, int right) {
int pivot = arr[right], // 选择最后一个作为基准
tail = left - 1; // tail 为小于基准的子数组的最后一个元素的下标
for (int i = left; i < right; i++) { // 遍历基准以外的其他元素
// 把小于等于基准的元素放到前一个子数组末尾
if (arr[i] <= pivot) {
swap(arr, ++tail, i); //交换两个位置的数值
}
}
// 最后把基准放到前一个子数组的后边，剩下的子数组既是大于基准的子数组
// 该操作很有可能把后面元素的稳定性打乱，所以快速排序是不稳定的排序算法
swap(arr,tail+1, right); //交换两个位置的数值
return tail + 1; // 返回基准的索引
}
双向寻找方式
思路：
- 取arr[0]为基准：pivot=arr[0]；
- 从后往前遍历，寻找比pivot小的数的下标right，直接arr[0]=arr[right]；
- 再从前往后遍历：第1位到第right-1位，寻找大于pivot的下标left，直接arr[right]=arr[left];
- 再从后往前遍历：第right-1位到第left+1位。。。
- 直到left==right，就是基准pivot所在位置。
例如：arr = {5, 7, 4, 6, 3, 1, 2, 9, 8}
a. 取出5
b. 从右往左找到比5小的数2，放到5原来的位置
c. 从左往右找到比5大的数7，放到2原来的位置
d. 直到左右两边寻找的下标相同，把5放到该位置，则比5小的都在左边，比5大的都在右边
e. 至此形成一个回合，重复递归遍历5左边和右边的区域。
public static void _quickSort(int[] arr,int left, int right) {
if (left < right) {
int mid = _partition(arr, left, right);
_quickSort(arr, left, mid-1);
_quickSort(arr, mid+1, right);
}
}
public static int _partition(int[] arr,int left, int right) {
// 取出第一个
int pivot = arr[left];
while (left < right){
// 从右往左找比pivot小的，放到pivot原来的位置
while (left < right && arr[right] >= pivot) {
right--;
}
arr[left] = arr[right];
// 从左往右找比pivot大的，放到上面寻找到的位置
while (left < right && arr[left] <= pivot) {
left++;
}
arr[right] = arr[left];
}
arr[left] = pivot;
return left;
}
5. 希尔排序(Shell Sort)
算法思想
希尔排序有时又叫做 “缩小间隔排序”，它以插入排序为基础，将原来要排序的列表划分为一些子列表，再对每一个子列表执行插入排序，从而实现对插入排序性能的改进。划分子列的特定方法是希尔排序的关键。
我们并不是将原始列表分成含有连续元素的子列，而是确定一个划分列表的增量 “i”，这个i更准确地说，是划分的间隔。然后把每间隔为i的所有元素选出来组成子列表，然后对每个子序列进行插入排序，最后当 i=1 时，对整体进行一次直接插入排序。
希尔排序是一种分组插入排序算法。
希尔排序每趟并不使某些元素有序，而是使整体数据越来越接近有序；最后一趟排序使得所有数据有序。
思路：
- 首先取一个整数d1=len/2，将元素分为d1个组，每组相邻量元素之间距离为d1，在各组内进行直接插入排序；
- 取第二个整数d2=d1/2，重复上述分组排序过程，直到di=1，即所有元素在同一组
public static void shellSort(int[] arr) {
for (int step = arr.length/2; step > 0 ; step/=2) {
for (int i = step; i < arr.length; i++) {
int value = arr[i];
int j;
for (j = i-step; j >= 0 && arr[j]>value; j-=step) {
arr[j+step] = arr[j];
}
arr[j+step] = value;
}
}
}
6. 归并排序
7. 堆排序 8. 基数排序 9. 桶排序归并排序是一种递归算法，它持续地将一个列表分成两半。如果列表是空的或者 只有一个元素，那么根据定义，它就被排序好了（最基本的情况）。如果列表里的元素超过一个，我们就把列表拆分，然后分别对两个部分调用递归排序。一旦这两个部分被排序好了，然后就可以对这两部分数列进行归并了。归并是这样一个过程：把两个排序好了的列表结合在一起组合成一个单一的有序的新列表。有自顶向下（递归法）和自底向上的两种实现方法。
若有不正之处，请谅解和批评指正，谢谢~
喜欢欢迎一件三连~
