排序算法
| 阅读：次
冒泡排序
通过与相邻元素的比较和交换来把小的数交换到最前面，时间复杂度为O(n^2)，空间复杂度为O(1)，与输入无关。
实现代码：
public class BubbleSort {
public static void bubbleSort(int[] arr) {
if(arr == null || arr.length == 0)
return ;
for(int i=0; i<arr.length-1; i++) {
for(int j=arr.length-1; j>i; j--) {
if(arr[j] < arr[j-1]) {
swap(arr, j-1, j);
}
}
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
冒泡排序缺陷：
1.在排序过程中，执行完当前的第i趟排序后，可能数据已全部排序完备，但是程序无法判断是否完成排序，会继续执行剩下的(n-1-i)趟排序。解决方法：设置一个flag位, 如果一趟无元素交换，则 flag = 0; 以后再也不进入第二层循环。
2.当排序的数据比较多时排序的时间会明显延长，因为会比较 n*(n-1)/2次。
选择排序
和冒泡排序类似，都是在一次排序后把最小元素放到最前面，但是过程不同，冒泡排序是通过对整体的选择，而选择排序是通过对整体的选择。其实可以看成是对冒泡排序的优化，因为其目的相同，只是选择排序只有在确定了最小数的前提下才交换，大大减少了交换的次数，时间复杂度为O(n^2)，空间复杂度为O(1)，排序时间与输入无关。
实现代码：
public class SelectSort {
public static void selectSort(int[] arr) {
if(arr == null || arr.length == 0)
return ;
int minIndex = 0;
for(int i=0; i<arr.length-1; i++) { //只需要比较n-1次
minIndex = i;
for(int j=i+1; j<arr.length; j++) { //从i+1开始比较，因为minIndex默认为i了，i就没必要比了。
if(arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if(minIndex != i) { //如果minIndex不为i，说明找到了更小的值，交换之。
swap(arr, i, minIndex);
}
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
插入排序
将数据分为两部分，有序部分与无序部分，一开始有序部分包含第1个元素，依次将无序的元素插入到有序部分，直到所有元素有序。插入排序又分为直接插入排序、二分插入排序、链表插入等，这里只讨论直接插入排序。它是稳定的排序算法，时间复杂度为O(n^2)，空间复杂度为O(1)，排序时间与输入个数有关：输入元素的个数，元素已排序的程度。 最佳情况，输入数组是已经排好序的数组，运行时间是n的线性函数； 最坏情况，输入数组是逆序，运行时间是n^2。 实现代码：
public class InsertSort {
public static void insertSort(int[] arr) {
if(arr == null || arr.length == 0)
return ;
for(int i=1; i<arr.length; i++) { //假设第一个数位置时正确的；要往后移，必须要假设第一个。
int j = i;
int target = arr[i]; //待插入的
//后移
while(j > 0 && target < arr[j-1]) {
arr[j] = arr[j-1];
j --;
}
//插入
arr[j] = target;
}
}
}
快速排序
实际中最好的排序算法，但是不稳定，时间平均复杂度为O(nlgn)，最差情况下复杂度为O(n^2)，空间复杂度为O(lgn)。总结来说就是：冒泡+二分+递归分治
快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是 O(n^2)，它的平均时间复杂度为 O(nlogn)。其实快速排序是基于 “二分” 的思想。
实现代码：
public class QuickSort {
private static void quickSort(int[] a) {
quickSort(a, 0, a.length - 1);
}
private static void quickSort(int[] a, int left, int right) {
if (left < right) {
int pivot = a[left];
int lo = left;
int hi = right;
while (lo < hi) {
while (lo < hi && a[hi] >= pivot) {
hi--;
}
a[lo] = a[hi];
while (lo < hi && a[lo] <= pivot) {
lo++;
}
a[hi] = a[lo];
}
a[lo] = pivot;
quickSort(a, left, lo - 1);
quickSort(a, lo + 1, right);
}
}
}
希尔排序
是插入排序的一种更高效的改进版本。它的作法不是每次一个元素挨一个元素的比较。而是初期选用大跨步（增量较大）间隔比较，使记录跳跃式接近它的排序位置；然后增量缩小；最后增量为 1 ，这样记录移动次数大大减少，提高了排序效率。希尔排序对增量序列的选择没有严格规定。 希尔排序是基于插入排序的以下两点性质而提出改进方法的：
- 插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率
- 但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位
算法思路：
1、先取一个正整数 d1(d1 1 个组，所有距离为 d1 的倍数的记录看成一组，然后在各组内进行插入排序
2、然后取 d2(d2 1)
3、重复上述分组和排序操作；直到取 di = 1(i >= 1) 位置，即所有记录成为一个组，最后对这个组进行插入排序。一般选 d1 约为 n/2，d2 为 d1 /2， d3 为 d2/2 ，…， di = 1。
实例分析：
从上述排序过程可见，希尔排序的特点是，子序列的构成不是简单的逐段分割，而是将某个相隔某个增量的记录组成一个子序列。如上面的例子，第一趟排序时的增量为5，第二趟排序的增量为3。由于前两趟的插入排序中记录的关键字是和同一子序列中的前一个记录的关键字进行比较，因此关键字较小的记录就不是一步一步地向前挪动，而是跳跃式地往前移，从而使得进行最后一趟排序时，整个序列已经做到基本有序，只要作记录的少量比较和移动即可。因此希尔排序的效率要比直接插入排序高。
实现代码：
public class ShellSort {
public static void shellInsert(int[] arr, int d) {
for(int i=d; i<arr.length; i++) {
int j = i - d;
int temp = arr[i]; //记录要插入的数据
while (j>=0 && arr[j]>temp) { //从后向前，找到比其小的数的位置
arr[j+d] = arr[j]; //向后挪动
j -= d;
}
if (j != i - d) //存在比其小的数
arr[j+d] = temp;
}
}
public static void shellSort(int[] arr) {
if(arr == null || arr.length == 0)
return ;
int d = arr.length / 2;
while(d >= 1) {
shellInsert(arr, d);
d /= 2;
}
}
}
归并排序
其基本思想是，先递归划分子问题，然后合并结果。把待排序列看成由两个有序的子序列，然后合并两个子序列，然后把子序列看成由两个有序序列。。。。。倒着来看，其实就是先两两合并，然后四四合并。。。最终形成有序序列。空间复杂度为O(n)，时间复杂度为O(nlogn)，时间与输入无关。
举例：
实现代码：
public class MergeSort {
public static void mergeSort(int[] arr) {
mSort(arr, 0, arr.length-1);
}
public static void mSort(int[] arr, int left, int right) {
if(left >= right)
return ;
int mid = (left + right) / 2;
mSort(arr, left, mid); //递归排序左边
mSort(arr, mid+1, right); //递归排序右边
merge(arr, left, mid, right); //合并
}
public static void merge(int[] arr, int left, int mid, int right) {
//[left, mid] [mid+1, right]
int[] temp = new int[right - left + 1]; //中间数组
int i = left;
int j = mid + 1;
int k = 0;
while(i <= mid && j <= right) {
if(arr[i] <= arr[j]) {
temp[k++] = arr[i++];
}
else {
temp[k++] = arr[j++];
}
}
while(i <= mid) {
temp[k++] = arr[i++];
}
while(j <= right) {
temp[k++] = arr[j++];
}
for(int p=0; p<temp.length; p++) {
arr[left + p] = temp[p];
}
}
}
总结
- 从平均时间来看，快速排序是效率最高的，但快速排序在最坏情况下的时间性能不如堆排序和归并排序。而后者相比较的结果是，在n较大时归并排序使用时间较少，但使用辅助空间较多。
- 上面说的简单排序包括除希尔排序之外的所有冒泡排序、插入排序、简单选择排序。其中直接插入排序最简单，但序列基本有序或者n较小时，直接插入排序是好的方法，因此常将它和其他的排序方法，如快速排序、归并排序等结合在一起使用。
- 基数排序的时间复杂度也可以写成O(d*n)。因此它最使用于n值很大而关键字较小的的序列。若关键字也很大，而序列中大多数记录的最高关键字均不同，则亦可先按最高关键字不同，将序列分成若干小的子序列，而后进行直接插入排序。
- 从方法的稳定性来比较，基数排序是稳定的内排方法，所有时间复杂度为O(n^2)的简单排序也是稳定的。但是快速排序、堆排序、希尔排序等时间性能较好的排序方法都是不稳定的。稳定性需要根据具体需求选择。
- 上面的算法实现大多数是使用线性存储结构，像插入排序这种算法用链表实现更好，省去了移动元素的时间。具体的存储结构在具体的实现版本中也是不同的。
感谢您的支持，我会继续努力的!
打开支付宝扫一扫，即可进行扫码打赏哦