概述
本文主要介绍面试常见的几种排序算法的基本思想、复杂度及其Java实现。包括冒泡、简单选择、直接插入和快速排序。
- 算法稳定性：假设在数列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的！否则不稳定！
- 内排序：所有排序操作都在内存中完成；
- 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行
-
排序算法分类
排序算法分类
1. 冒泡排序(Bubble Sort)
基本思想
- 冒泡排序就是把较小的元素往前调或者把较大的元素往后调。比较的是相邻的两个元素，交换也发生在这两个元素之间。所以，如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
-
算法原理：
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较
算法复杂度
- 若文件初状为正序，则一趟起泡就可完成排序，排序码的比较次数为n-1，且没有记录移动，时间复杂度——O(n)
- 若文件初态为逆序，则需要n-1趟起泡，每趟进行n-i次排序码的比较，且每次比较都移动三次，比较和移动次数均达到最大值——O(n2)
- 平均时间复杂度——O(n2)
算法实现(Java)
/**
* 冒泡排序
* @param arr
*/
public static void bubbleSort(int[] arr){
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j+1]){ //相邻元素两两比较
int temp = arr[j]; //元素交换
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
2. 简单选择排序(Simple Selection Sort)
基本思想
+每一趟从待排序的数据元素中选出最小（最大）的元素，顺序放在待排序的数列最前，直到全部待排序的数据元素全部排完。属于不稳定排序。
-
示例
图片.png
算法复杂度
最佳情况：T(n) = O(n2) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)
算法实现(Java)
/**
* 选择排序
* @param arr
*/
public static void selectSort(int[] arr){
for (int i = 0; i < arr.length; i++) {
for (int j = i+1; j < arr.length; j++) {
if (arr[i] > arr[j]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
3. 直接插入排序(Straight Insertion Sort)
基本思想
-
算法原理：
从整个待排序列中选出一个元素插入到已经有序的子序列中去，得到一个有序的、元素加一的子序列，直到整个序列的待插入元素为0，则整个序列全部有序。在实际的算法中，我们经常选择序列的第一个元素作为有序序列（因为一个元素肯定是有序的)， 我们逐渐将后面的元素插入到前面的有序序列中，直到整个序列有序。 -
算法描述
- 从第一个元素开始，该元素可以认为已经被排序；
- 取出下一个元素，在已经排序的元素序列中从后向前扫描；
- 如果该元素（已排序）大于新元素，将该元素移到下一位置；
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
- 将新元素插入到该位置后；
- 重复步骤2~5.
- 稳定性：如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。
-
示例
插入排序过程描述
算法复杂度
- 假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N)，需要遍历多少次呢？N-1！因此，直接插入排序的时间复杂度是O(N2)。T(n) = O(n2)
算法实现(Java)
/**
* 直接插入排序
* @param arr
*/
public static void insertSort(int[] arr){
for (int i = 1; i < arr.length; i++) {
int tmp = arr[i]; //设置哨兵，用于存储无序列表中取出的待插元素
int j = i - 1;
while (j >= 0 && arr[j] > tmp){
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = tmp;
}
}
4. 快速排序( Quick Sort )
基本思想
- 快速排序是对冒泡排序的一种改进。通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程递归进行，以此达到整个数据变成有序序列。
-
算法描述
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：- 从数列中挑出一个元素，称为 “基准”，通常选择第一个或者最后一个元素；
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列进行排序。
-
示例
一趟排序的过程描述
排序全过程描述
算法复杂度
T(n) = O(nlogn) ——当n较大时使用快排比较好，当序列基本有序时用快排反而不好。
算法实现(Java)
/**
* 快速排序---最好的情况是O(n)，最差的情况是O(n2)，平均：O(nlogn)
* 有两种实现方式！！！！
* @param arr
* @param low
* @param high
*/
public static void quickSort(int[] arr, int low, int high){
if (low > high) //low 和high分别为序列的第一个和最后一个元素的索引
return;
int start = low;
int end = high;
int key = arr[low]; //设定一个基准元素
while (start < end){
while (start < end && arr[end] >= key){
end--;
}
while (start < end && arr[start] <= key){
start++;
}
if (start < end){
swap(arr, start, end); //交换元素
}
}
swap(arr, low, start); //将基准元素插入到start==end的索引位置，至此第一趟排序过程结束
quickSort(arr, low, end-1);
quickSort(arr,end+1, high);
}
总结
种一棵树最好的时间是十年前，写一段代码最好的时间是现在！写的不好，欢迎批评指正！ 后边会陆续更新其它排序算法，如 堆排序、希尔排序、归并排序等！！
网友评论