- 冒泡排序 时间复杂度 O(n2)，空间复杂度 O(1)
- 选择排序 时间复杂度 O(n2)，空间复杂度 O(1)
- 插入排序 时间复杂度 O(n2)，空间复杂度 O(1)
- 希尔排序 时间复杂度 O(nlogn)，空间复杂度 O(1)
- 归并排序 时间复杂度 O(nlogn)，空间复杂度 O(n)
- 快速排序 时间复杂度 O(nlogn)，空间复杂度 O(logn)
- 堆排序
- 计数排序
- 桶排序
- 基数排序
冒泡排序
两两比较元素，使值较小的元素不断前移，值较大的元素不断后移，每次循环都能找出当前区间中值最大的元素，且循环结束时值最大的元素位于当前区间的最右端。
public static void bubbleSort(int[] array) {
for (int i = 0; i < array.length; i++) {
/*循环区间[0, len-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 selectionSort(int[] array) {
for (int i = 0; i < array.length; i++) {
int index = i;
/*当前区间[i, len)*/
for (int j = i; j < array.length; j++) {
if (array[j] < array[index]) {
index = j;
}
}
/*将当前区间中最小元素和区间头部元素互换*/
int temp = array[i];
array[i] = array[index];
array[index] = temp;
}
}
插入排序
在原数组上构建一个有序序列，初始时将a[0]视为有序序列，对于a[i]，从右到左扫描区间[o, i)，找到a[i]合适的插入位置，然后将区间[o, i)中大于a[i]的元素都后移一位，最后将a[i]插入到区间中，以此类推，直到所有元素均排序完毕。
public static void insertionSort(int[] array) {
for (int i = 1; i < array.length; i++) {
int current = array[i], j;
/*若current<array[j], 则array[j]后移一位*/
for (j = i-1; j >= 0; j--) {
if (current < array[j]) {
array[j+1] = array[j];
} else {
break;
}
}
array[j+1] = current;
}
}
希尔排序
希尔排序是插入排序的改进算法，不同点在于希尔排序会优先比较距离较远的元素。希尔排序也叫缩小增量排序，首先需要确定增量和缩小增量的模式，一般采用增量gap = length / 2，缩小增量gap = gap / 2，从而得到增量序列{n/2, (n/2)/2 … 1}。增量序列的长度k表示算法需要对数组进行排序的次数，增量值gap表示每次排序需将数组划分成gap组，分组提取元素时的步长为gap，对于每个分组，按照插入排序的方式进行处理。
public static void ShellSort(int[] array) {
/*确定增量*/
int gap = array.length / 2;
while (gap > 0) {
/*分成gap组, 当前指向分组中第二个元素*/
for (int i = gap; i < array.length; i++) {
int current = array[i], j;
/*若current<array[j], 则array[j]后移一位*/
for (j = i-gap; j >= 0; j = j-gap) {
if (current < array[j]) {
array[j+gap] = array[j];
} else {
break;
}
}
array[j+gap] = current;
}
/*确定缩小增量*/
gap /= 2;
}
}
归并排序
（分治法）以二路归并排序为例，首先将当前数组分成两个子串，递归分割子串，直到每个子串中只包含一个元素，这时可以认为子串内部是有序的，然后将子串两两合并，使子串间有序，不断合并有序的子串，最终得到一个有序的数组。
public static int[] MergeSort(int[] array) {
/*递归终止条件*/
if (array.length < 2) {
return array;
}
int mid = array.length / 2;
/*2-路归并, 将array分成两段*/
int[] left = Arrays.copyOfRange(array, 0, mid);
int[] right = Arrays.copyOfRange(array, mid, array.length);
/*使两个子段内部有序*/
/*合并内部有序的子串, 使整体有序*/
return merge(MergeSort(left), MergeSort(right));
}
/**
* 将两段排序好的数组结合成一个排序数组
* @param left
* @param right
*/
public static int[] merge(int[] left, int[] right) {
int[] res = new int[left.length + right.length];
for (int index = 0,i = 0,j = 0; index < res.length; index++) {
/*left遍历完*/
if (i >= left.length) {
res[index] = right[j++];
} else if (j >= right.length) {
res[index] = left[i++];
} else if (left[i] < right[j]) {
res[index] = left[i++];
} else {
res[index] = right[j++];
}
}
return res;
}
快速排序
（分治法）从当前数组中挑出一个元素作为基准，将小于基准的元素放在基准的左边，大于基准的元素放在基准右边，从而得到基准的左子串和右子串，然后按照上述规则递归处理左子串和右子串，最终得到一个有序的数组。
public static void QuickSort(int[] array, int low, int high) {
/*递归终止条件, 如果子串中只有一个元素则不处理*/
if (low >= high) {
return;
}
int i = low, j = high, pivot = array[low], temp;
while (i < j) {
/*必须先处理j, 保证该轮结束后是较小数和基准数互换*/
while (pivot <= array[j] && i < j) {
j--;
}
while (pivot >= array[i] && i < j) {
i++;
}
/*互换array[i]和array[j], 使数列相对有序*/
if (i < j) {
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
/*基准数和ij互换*/
array[low] = array[i];
array[i] = pivot;
/*递归调用左半数组*/
QuickSort(array, low, j-1);
//递归调用右半数组
QuickSort(array, j+1, high);
}
堆排序
堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
首先根据数组构建一个无序的完全二叉树，根据堆积的性质将二叉树转换成堆积，转换完成后根节点即为当前数组中的最大值，将根节点与树中最后一个叶子节点互换，并删除该叶子节点，此时完全二叉树又变成了无序状态，按照上述规则类推，直到树为空。
(10条消息) 超详细十大经典排序算法总结（java代码）c或者cpp的也可以明白Top_Spirit的博客-CSDN博客排序算法
