提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
文章目录- 一、算法实现
- 1.冒泡排序
- 2.选择排序
- 3.插入排序
- 4.希尔排序
- 5.快速排序
- 6.归并排序
- 7.堆排序
- 8.基数排序
- 二、稳定性分析
- 1.冒泡排序
- 2.选择排序
- 3.插入排序
- 4.希尔排序
- 5.快速排序
- 6.归并排序
- 7.堆排序
- 8.基数排序
- 稳定性总结
一、算法实现 1.冒泡排序
1).将序列中所有的元素两两比较，将最小的放在最前面；
2).将剩余序列中所有的元素两两比较，将最小的放在最前面；
3).重复第二步，直到只剩下一个数。
代码如下（示例）：
import java.util.Arrays;
public class BubbleSortDemo {
public static void main(String[] args) {
int[] array = {1, 4, 2, 8, 5, 7, 3, 6, 9, 0};
System.out.println(Arrays.toString(array));
bubbleSort(array);
System.out.println(Arrays.toString(array));
}
private static void bubbleSort(int[] arr) {
boolean flag = true;
for(int i = 0; i < arr.length && flag; i++) {
flag = false;
for(int j = arr.length - 1; j > i; j--) {
//升级版的冒泡，最好时间复杂度可以是O(n)
if(arr[j] < arr[j - 1]) {
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
flag = true;
}
}
}
}
private static void bubbleSortOld(int[] arr) {
for(int i = 0; i < arr.length - 1; i++) {
for(int j = i + 1; j < arr.length; j++) {
//最基础的冒泡，即使有序，时间复杂度也是O(n²)
if(arr[i] > arr[j]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
}
时间复杂度(平均)：O(n²) 时间复杂度(最好)：O(n) 时间复杂度(最坏)：O(n²)
空间复杂度：O(1) 稳定性：稳定
1.遍历整个序列，将最小的数放在前面；
2.遍历剩下的序列，将最小的数放在最前面；
3.重复第二步，直到只剩下一个数。
代码如下（示例）：
import java.util.Arrays;
public class SelectionSortDemo {
public static void main(String[] args) {
int[] array = {1, 4, 2, 8, 5, 7, 3, 6, 9, 0};
System.out.println(Arrays.toString(array));
selectionSort(array);
System.out.println(Arrays.toString(array));
}
private static void selectionSort(int[] arr) {
for(int i = 0; i < arr.length - 1; i++) {
int min = i;
for(int j = i + 1; j < arr.length; j++) {
if(arr[j] < arr[min]) min = j;
}
if(min != i) {
int temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}
}
}
时间复杂度(平均)：O(n²) 时间复杂度(最好)：O(n²) 时间复杂度(最坏)：O(n²)
空间复杂度：O(1) 稳定性：不稳定
3.插入排序
1.将第一个元素和第二个元素排序，然后构成一个有序序列；
2.将第三个元素插入进去，构成一个新的有序序列；
3.对第四个元素、第五个元素……直到最后一个数，重复第二步。
代码如下（示例）：
import java.util.Arrays;
public class InsertSortDemo {
public static void main(String[] args) {
int[] array = {1, 4, 2, 8, 5, 7, 3, 6, 9, 0};
System.out.println(Arrays.toString(array));
insertionSort(array);
System.out.println(Arrays.toString(array));
}
private static void insertionSort(int[] arr) {
for(int i = 0; i < arr.length - 1; i++) {
for(int j = i + 1; j > 0; j--) {
//如果当前元素比上一个元素小，就交换
if(arr[j] >= arr[j - 1]) break;
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
}
}
}
时间复杂度(平均)：O(n²) 时间复杂度(最好)：O(n) 时间复杂度(最坏)：O(n²)
空间复杂度：O(1) 稳定性：稳定
4.希尔排序
1.将元素个数设为n，取奇数k=n/2，将下标差值为k的元素分为一组，构成有序序列；
2.再取k=k/2，将下标差值为k的元素分为一组，构成有序序列；
3.重复第二步，直到k=1执行简单插入排序。
代码如下（示例）：
import java.util.Arrays;
public class ShellSortDemo {
public static void main(String[] args) {
int[] array = {1, 4, 2, 8, 5, 7, 3, 6, 9, 0};
System.out.println(Arrays.toString(array));
shellSort(array);
System.out.println(Arrays.toString(array));
}
private static void shellSort(int[] arr) {
for(int gap = arr.length / 2; gap > 0; gap /= 2) {
for(int j = 0; (j + gap) < arr.length; j++) {
for(int k = 0; (k + gap) < arr.length; k += gap) {
if(arr[k] > arr[k + gap]) {
int temp = arr[k + gap];
arr[k + gap] = arr[k];
arr[k] = temp;
}
}
}
}
}
}
时间复杂度（平均）：O(n^1.3) 时间复杂度(最好)：O(n) 时间复杂度(最坏)：O(n²)
空间复杂度：O(1) 稳定性：不稳定
5.快速排序
1.选择第一个数为p，小于p的放在左边，大于p的数放在右边；
2.递归地将p左边和右边的数都按照第一步进行，直到不能递归。
代码如下（示例）：
import java.util.Arrays;
public class QuickSortDemo {
public static void main(String[] args) {
int[] array = {1, 4, 2, 8, 5, 7, 3, 6, 9, 0};
System.out.println(Arrays.toString(array));
quickSort(array, 0, array.length - 1);
System.out.println(Arrays.toString(array));
}
private static void quickSort(int[] array, int left, int right) {
if(left > right) return;
int i = left, j = right, base = array[left];
while(i < j) {
while(i < j && array[j] > base) j--;
while(i < j && array[i] <= base) i++;
if(i < j) swap(array, i, j);
}
swap(array, i, left);
quickSort(array, left, i - 1);
quickSort(array, i + 1, right);
}
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
时间复杂度（平均）：O(nlogn) 时间复杂度(最好)：O(nlogn) 时间复杂度(最坏)：O(n²)
空间复杂度：O(logn) 稳定性：不稳定
6.归并排序
1.选择相邻两个数成为一个有序序列；
2.选择相邻的两个有序序列组成一个有序序列；
3.重复第二步，直到全部成为一个有序序列。
代码如下（示例）：
import java.util.Arrays;
public class MergeSortDemo {
public static void main(String[] args) {
int[] array = {1, 4, 2, 8, 5, 7, 3, 6, 9, 0};
System.out.println(Arrays.toString(array));
mergeSort(array, 0, array.length - 1);
System.out.println(Arrays.toString(array));
}
private static void mergeSort(int[] array, int start, int end) {
if(start < end) {
int mid = (start + end) / 2;
mergeSort(array, start, mid);
mergeSort(array, mid + 1, end);
merge(array, start, mid, end);
}
}
private static void merge(int[] array, int left, int mid, int right) {
int[] temp = new int[array.length];
int p1 = left, p2 = mid + 1, k = left;
while(p1 <= mid && p2 <= right) {
if(array[p1] <= array[p2]) temp[k++] = array[p1++];
else temp[k++] = array[p2++];
}
while(p1 <= mid) temp[k++] = array[p1++];
while(p2 <= right) temp[k++] = array[p2++];
for(int i = left; i <= right; i++) {
array[i] = temp[i];
}
}
}
时间复杂度（平均）：O(nlogn) 时间复杂度(最好)：O(nlogn) 时间复杂度(最坏)：O(nlogn)
空间复杂度：O(n) 稳定性：稳定
7.堆排序
1.将序列构建成大顶堆；
2.将根节点与最后一个节点交换，然后断开最后一个节点；
3.重复第一、第二步，直到所有的节点都断开。
代码如下（示例）：
import java.util.Arrays;
public class HeapSortDemo {
public static void main(String[] args) {
int[] array = {1, 4, 2, 8, 5, 7, 3, 6, 9, 0};
System.out.println(Arrays.toString(array));
heapSort(array);
System.out.println(Arrays.toString(array));
}
private static void heapSort(int[] array) {
//1.构建大顶堆
for(int i = array.length / 2 - 1; i >= 0; i--) {
//从一个非叶子节点从下至上，从右至左调整结构
adjustHeap(array, i, array.length);
}
//2.交换堆顶元素与末尾元素，并调整堆结构
for(int j = array.length - 1; j > 0; j--) {
swap(array, 0, j);
adjustHeap(array, 0, j);
}
}
private static void adjustHeap(int[] array, int i, int length) {
int temp = array[i];
//从i节点的左子节点开始，也就是2i + 1 开始
for(int k = i * 2 + 1; k < length; k = k * 2 + 1) {
//如果左子节点小于右子节点，k指向右子节点
if(k + 1 < length && array[k] < array[k + 1]) k++;
if(array[k] > temp) { //子节点大于父节点，将子节点赋值给父节点
array[i] = array[k];
i = k;
} else break;;
}
array[i] = temp;
}
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
时间复杂度（平均）：O(nlogn) 时间复杂度(最好)：O(nlogn) 时间复杂度(最坏)：O(nlogn)
空间复杂度：O(1) 稳定性：不稳定
8.基数排序
1.将所有的数的个位数取出，按照个位数进行排序，构成一个序列；
2.将新构成的所有数的十位数取出，按照十位数进行排序，构成一个序列；
3.重复 *** 作，直至最大位数。
代码如下（示例）：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class BasicSortDemo {
public static void main(String[] args) {
int[] array = {1, 4, 2, 8, 5, 7, 3, 6, 9, 0};
System.out.println(Arrays.toString(array));
basicSort(array);
System.out.println(Arrays.toString(array));
}
private static void basicSort(int[] array) {
List> dyadic = new ArrayList<>();
for(int i = 0; i < 10; i++) {
ArrayList arr = new ArrayList<>();
dyadic.add(arr);
}
int max = 0;
for (int item : array) {
if (item > max) max = item;
}
int times = 0;//判断最大值为几位数，其位数就是应该循环的次数
while(max > 0) {
max /= 10;
times++;
}
for(int i = 0; i < times; i++) {
for (int value : array) {
int x = value % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
//将该数组作为下标，找到对应的子数组，将该元素添加到子数组中,并更新大数组
ArrayList arr = dyadic.get(x);
arr.add(value);
dyadic.set(x, arr);
}
}
int index = 0; //将子数组依次遍历，将每个子数组中的元素添加到array中
for(int k = 0; k < 10; k++) {
while(dyadic.get(k).size() > 0) {
ArrayList arr = dyadic.get(k);
array[index] = (int)arr.get(0);
arr.remove(0);
index++;
}
}
}
}
时间复杂度（平均）：O(nk) 时间复杂度(最好)：O(nk) 时间复杂度(最坏)：O(n*k)
空间复杂度：O(n+k) 稳定性：稳定
二、稳定性分析
排序算法的稳定性：在待排序的序列中，有相同元素，排完序后相同元素的相对位置保持不变，比如在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，这种排序算法就是稳定的。
1.冒泡排序冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。两个元素相等，就不会交换位置了；如果两个相等的元素不相邻，即使两两交换把两个相邻起来，这时候也不会再交换，所以相同元素的前后顺序并没有改变，因此冒泡排序是稳定排序算法。
2.选择排序选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推。在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么 交换后稳定性就被破坏了。举个例子，序列5 8 5 2 9，第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。
3.插入排序插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。
4.希尔排序希尔排序是按照不同步长对元素进行插入排序。一次插入排序是稳定的，不会改变相同元 素的相对顺序，由于有多次插入排序，在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。
5.快速排序快速排序有两个方向，左边的i下标一直往右走，当a[i] <= a[center_index]，其中center_index是中枢元素的数组下标，一般取为数组第0个元素。而右边的j下标一直往左走，当a[j] > a[center_index]。如果i和j都走不动了，i <= j, 交换a[i]和a[j],重复上面的过程，直到i>j。 交换a[j]和a[center_index]，完成一趟快速排序。在中枢元素和a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为 5 3 3 4 3 8 9 10 11， 现在中枢元素5和3(第5个元素，下标从1开始计)交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和a[j] 交换的时刻。
6.归并排序归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素(认为直接有序)或者2个元素(1次比较和交换),然后把各个有序的段序列合并成一个有 序的长序列，不断合并直到原序列全部排好序。在1个不会交换，2个元素如果大小相等也没必要交换，所以不会破坏稳定性。合并过程中我们可以保证如果两个当前元素相等时，把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。因此归并排序也是稳定的排序算法。
7.堆排序堆的结构是节点i的孩子为2i和2i+1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n的序列，堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n /2-1, n/2-2, …1这些个父节点选择元素时，就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1个父节点把后面一个相同的元素没有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法。
8.基数排序基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。基数排序基于分别排序，分别收集，相同元素无需排序，不会改变前后顺序，所以其是稳定的排序算法。
稳定性总结稳定排序算法： 冒泡排序、插入排序、归并排序、基数排序
不稳定排序算法： 选择排序、快速排序、希尔排序、堆排序
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）