前言：可以通过目录来找你需要的排序的源代码。先是解释底层原理，后附带代码。
目录
稳定的概念
一、插入排序
二、希尔排序
三、选择排序
四、堆排序
五、冒泡排序
六、快速排序
七、归并排序
八、排序总结
额外：计数排序
稳定的概念
稳定性：
相同元素的相对位置排序完没有改变，则为稳定排序。 若排序后相同元素的相对位置发生变化，则为不稳定排序。
一、插入排序
原理如下：
从数据的第2位开始，跟前面的比，找到比该数据小的值插到后面，没有的话插到最前面。
代码思路：
从第2位开始记为j，让j++把每一位都插到前面去。然后让j的前一位记为i，i--，让j从i开始往前插入。直到全插完。
插入排序特性总结：
1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定
//插入排序
/*
1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定
*/
public void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int tmp = arr[i];
int j = i - 1;
for (; j >= 0; j--) {
if (arr[j] > tmp) {
arr[j + 1] = arr[j];
} else {
break;
}
}
//若j<0时，for循环进不来，所以再次放到0下标
arr[j + 1] = tmp;
}
}
二、希尔排序
算法原理：
实际上就是插入排序的优化！插入排序一个一个插太慢了，这时希尔排序就出来了，把数据分多组，让他们先插入排序，然后缩短组数，再排序，循环，直到排完序。
代码思路：
我们先把一组数据总数/2分为gap组，先让gap组排序，然后gap/2，排序 ，循环往复，直到排完。如下图，若gap=2时，我们只需要arr[j]=arr[j+gap]和tmp就能交换插入了，gap=2有2轮，但是剩下一轮就只能再fori一次，若让i++就能交替循环，一次fori就能搞定了。
希尔排序特性：
时间复杂度：O(N^1.25)到O(1.6 * N^1.25)（业内还没有准确的，只有个大概的）
稳定性：不稳定
//希尔排序
/*
*
* 因为咋们的gap是按照Knuth提出的方式取值的，而且Knuth进行了大量的试验统计，我们暂时就按照：
* O(N^1.25)到O(1.6 * N^1.25)来算。
稳定性：不稳定
* */
public void shellSort(int[] arr) {
int gap = arr.length;
while (gap > 1) {
gap /= 2;
shell(gap, arr);
}
}
private void shell(int gap, int[] arr) {
for (int i = gap; i < arr.length; i++) {
int tmp = arr[i];
int j = i - gap;
for (; j >= 0; j -= gap) {
if (arr[j] > tmp) {
arr[j + gap] = arr[j];
} else {
break;
}
}
arr[j + gap] = tmp;
}
}
三、选择排序
原理如下：
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元 素排完 。
代码思路：
把第一个值作为tmp，然后i++往后循环，如果有小于tmp的就替换tmp，就找到最小的了，把它放到j（j=i+1）里面。for循环走完arr.length就排完序了。
插入排序特性总结：
1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
//选择排序
/*
1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
*/
public void selectSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
int minindex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minindex]) {
minindex = j;
}
}
swap(arr, minindex, i);
}
}
private void swap(int[] arr, int minindex, int i) {
int tmp = arr[minindex];
arr[minindex] = arr[i];
arr[i] = tmp;
}
//选择排序的优化(最大最小一起判断)
public void selectSort2(int[] arr) {
int left = 0;
int right = arr.length - 1;
while (left < right) {
int minindex = left;
int maxindex = left;
for (int i = left + 1; i <= right; i++) {
if (arr[i] < arr[minindex]) {
minindex = i;
}
if (arr[i] > arr[maxindex]) {
maxindex = i;
}
}
swap(arr, minindex, left);
swap(arr, maxindex, right);
left++;
right--;
}
}四、堆排序
原理如下：
因为堆是有顺序的，不是大根堆就是小根堆。就是倒置一下顺序，逆序一下。我们只需要将最后一个排序跟堆首调换一下，然后向下调整，每个都如此，直到排完序。
代码思路：
比如大根堆，只需要将end=arr.length-1的元素和堆首元素交换，然后将堆首元素向下调整（找到两个根最大的那一个根，交换），然后end--。
插入排序特性总结：
1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
//堆排序
/*
1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
*/
public void heapSort(int[] arr) {
createBigHeap(arr);
int end = arr.length - 1;
while (end >= 0) {
swap(arr, 0, end);
siftDown(0, arr, end);
end--;
}
}
private void createBigHeap(int[] array) {
for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
siftDown(parent, array, array.length);
}
}
private void siftDown(int parent, int[] array, int end) {
int child = 2 * parent + 1;
while (child < end) {
if (child + 1 < end && array[child] < array[child + 1]) {
child++;
}
//child下标 就是左右孩子最大值的下标
if (array[child] > array[parent]) {
swap(array, child, parent);
parent = child;
child = 2 * parent + 1;
} else {
break;
}
}
}
private void swap(int[] arr, int minindex, int i) {
int tmp = arr[minindex];
arr[minindex] = arr[i];
arr[i] = tmp;
}五、冒泡排序
原理如下：
一趟一趟来，将小的数和大数交换，每一趟都可以将最大的一个数放到最后。所有趟数走完，将排序完成。
代码思路：
两层循环，第一层控制趟数为arr.length-1，第二层arr.length-1-i表示一趟中交换的次数。定义一个tmp来交换，如果后面的数比前面的数小，则交换，如果大于，就用大于的这个数和后面交换。
优化：可能循环一次就排完序了，剩下的就浪费时间了。我们可以定义一个flg，如果一趟下来都不需要交换，证明完成了，结束2层循环。
插入排序特性总结：
1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定
//冒泡排序
/*
1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定
*/
public void buddleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
boolean flg = false;
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
flg = true;
}
}
if (!flg) {
break;
}
}
}
六、快速排序
原理如下：
找基准，通常是第一个元素，然后小于它的放左边，大于他的放右边。然后下一组又是这一组的第一个，直到所有元素都排完序。
代码思路：
1.递归：每次递归都找第一个为基准，然后<基准，放左边；>基准放右边。直到start<end，就排完序。
2.非递归：
- 将待排序的序列的首尾元素的下标入栈。
- 当栈不为空时，取出栈顶的下标，将序列的首尾元素作为基准值进行分区操作。
- 分区操作的目的是将比基准值小的元素放到基准值的左边，比基准值大的元素放到基准值的右边，并返回基准值的下标。
- 将分区操作后的左右子序列的首尾元素的下标入栈，注意先将右子序列的下标入栈，再将左子序列的下标入栈。
- 重复步骤2-4，直到栈为空。
优化：
1. 三数取中法选key
2. 递归到小的子区间时，可以考虑使用插入排序
插入排序特性总结：
1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(logN)
4. 稳定性：不稳定
递归
//快速排序
/*
1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(logN)
4. 稳定性：不稳定
*/
public void quickSort(int[] arr) {
quick(arr, 0, arr.length - 1);
}
public void quick(int[] arr, int start, int end) {
if (start >= end) {
return;
}
if (end - start + 1 <= 10) {
insertSortRange(arr, start, end);
return;
}
//三数取中(优化)
int index = midThreeNum(arr, start, end);
swap(arr, index, start);
int par = partition(arr, start, end);
quick(arr, start, par - 1);
quick(arr, par + 1, end);
}
public static void insertSortRange(int[] array, int left, int right) {
for (int i = left + 1; i <= right; i++) {
int tmp = array[i];
int j = i - 1;
for (; j >= left; j--) {
if (array[j] > tmp) {
array[j + 1] = array[j];
} else {
break;
}
}
array[j + 1] = tmp;
}
}
public int partitionHoard(int[] arr, int left, int right) {
int tmp = arr[left];
int i = left;
while (left < right) {
while (left < right && arr[right] >= tmp) {
right--;
}
while (left < right && arr[left] <= tmp) {
left++;
}
swap(arr, left, right);
}
swap(arr, left, i);
return left;
}
//挖坑法
public int partition(int[] arr, int left, int right) {
int tmp = arr[left];
while (left < right) {
while (left < right && arr[right] >= tmp) {
right--;
}
arr[left] = arr[right];
while (left < right && arr[left] <= tmp) {
left++;
}
arr[right] = arr[left];
}
arr[left] = tmp;
return left;
}
//返回值是中位数的下标(优化快排)
private static int midThreeNum(int[] array, int left, int right) {
int mid = (left + right) / 2;
if (array[left] < array[right]) {
if (array[mid] < array[left]) {
return left;
} else if (array[mid] > array[right]) {
return right;
} else {
return mid;
}
} else {
if (array[mid] < array[right]) {
return right;
} else if (array[mid] > array[left]) {
return left;
} else {
return mid;
}
}
}非递归
//非递归快速排序
public void quickSortNor(int[] arr) {
Stack<Integer> stack = new Stack<>();
int left = 0;
int right = arr.length - 1;
int par = partition(arr, left, right);
if (par > left + 1) {
stack.push(left);
stack.push(par - 1);
}
if (par < right - 1) {
stack.push(par + 1);
stack.push(right);
}
while (!stack.isEmpty()) {
right = stack.pop();
left = stack.pop();
par = partition(arr, left, right);
if (par > left + 1) {
stack.push(left);
stack.push(par - 1);
}
if (par < right - 1) {
stack.push(par + 1);
stack.push(right);
}
}
}
七、归并排序
原理如下：
将一组数据递归分成2对，4对....直到分成单一的元素。最后一对一对排序后回来...4对，2对，1对给它排序，直到排完序。
代码思路：
递归把数据都分成单一的元素，然后合并，合并的话需要创建一个新的数组tmp，定义s1，e1，s2，e2表示分成2份的数组的头和尾，让s1和s2比较，如果s1比s2小，让s1进入tmp数组，否则反之。若一份数组走完了，另一份数组没有，则让另一份数组while循环进入tmp。
插入排序特性总结：
1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定
//合并排序
/*
1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定
*/
public void mergeSort(int[] arr) {
mergeSortFun(arr, 0, arr.length - 1);
}
public void mergeSortFun(int[] arr, int left, int right) {
if (left >= right) {
return;
}
int mid = (right + left) / 2;
mergeSortFun(arr, left, mid);
mergeSortFun(arr, mid + 1, right);
//合并
merge(arr, left, mid, right);
}
private void merge(int[] arr, int left,
int mid, int right) {
int k = 0;
int[] tmp = new int[right - left + 1];
int s1 = left;
int e1 = mid;
int s2 = mid + 1;
int e2 = right;
while (s1 <= e1 && s2 <= e2) {
if (arr[s1] <= arr[s2]) {
tmp[k++] = arr[s1++];
} else {
tmp[k++] = arr[s2++];
}
}
while (s1 <= e1) {
tmp[k++] = arr[s1++];
}
while (s2 <= e2) {
tmp[k++] = arr[s2++];
}
//拷贝
for (int i = 0; i < k; i++) {
arr[i + left] = tmp[i];
}
}
//合并排序非递归
public void mergeSortNor(int[] array) {
int gap = 1;
while (gap < array.length) {
for (int i = 0; i < array.length; i = i + 2 * gap) {
int left = i;
int mid = left + gap - 1;
if (mid >= array.length) {
mid = array.length - 1;
}
int right = mid + gap;
if (right >= array.length) {
right = array.length - 1;
}
merge(array, left, mid, right);
}
gap *= 2;
}
}
八、排序总结
| 排序方法 | 最好 | 平均 | 最坏 | 时间复杂度 | 空间复杂度 |
| 冒泡排序 | O(N) | O(N^2) | O(N^2) | O(1) | 稳定 |
| 插入排序 | O(N) | O(N^2) | O(N^2) | O(1) | 稳定 |
| 选择排序 | O(N^2) | O(N^2) | O(N^2) | O(1) | 不稳定 |
| 希尔排序 | O(N) | O(N^1.3) | O(n^2) | O(1) | 不稳定 |
| 堆排序 | O(N * log(N)) | O(N * log(N)) | O(N * log(N)) | O(1) | 不稳定 |
| 快速排序 | O(N * log(N)) | O(N * log(N)) | O(N^2) | O(log(N)) ~ O(N) | 不稳定 |
| 归并排序 | O(N * log(N)) | O(N * log(N)) | O(N * log(N)) | O(N) | 稳定 |
额外：计数排序
//计数排序
/*
1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
2. 时间复杂度：O(MAX(N,范围))
3. 空间复杂度：O(范围)
4. 稳定性：稳定
*/
public void countSort(int[] array) {
//1. 遍历数组 求最大值 和 最小值
int maxVal = array[0];
int minVal = array[0];
for (int i = 0; i < array.length; i++) {
if (maxVal < array[i]) {
maxVal = array[i];
}
if (minVal > array[i]) {
minVal = array[i];
}
}
//2. 定义count数组
int[] count = new int[maxVal - minVal + 1];
//3. 遍历array数组 把值 放入 计数数组当中
for (int i = 0; i < array.length; i++) {
int val = array[i];//98
count[val - minVal]++;
}
//4. 以上3步完成之后，计数数组 已经存好了对应的数据
// 接下来 开始遍历 计数数组
int index = 0;//array的下标
for (int i = 0; i < count.length; i++) {
while (count[i] > 0) {
array[index] = i + minVal;
index++;
count[i]--;
}
}
}