锁清秋
常见排序算法
排序的分类
- 内部排序:
指将需要处理的所有数据都加载到内部存储器中进行排序。
- 外部排序法：
数据量过大，无法全部加载到内存中，需要借助外部存储进行
排序。
1、冒泡排序
基本介绍
冒泡排序（Bubble Sorting）的基本思想是：通过对待
排序序列从前向后（从下标较小的元素开始）,依次比较
相邻元素的值，若发现逆序则交换，使值较大
的元素逐渐从前移向后部，就象水底下的气泡一样逐渐
向上冒
排序过程
在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。
代码示例
public static void bubbleSort(int[] arr) {for (int i = 0; i < arr.length - 1; i++) {//确定排序趟数//这里length - 1 -i, i表示前面的i次循环已经把大的数移动到后部分了,//所以后部分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;}}}}
简单优化
因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较
代码示例
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
Boolean flag = false;
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;
flag = true;
}
}
if (!flag) {
break;
}
}
}
2、选择排序
基本介绍
选择式排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的
选择排序思想
选择排序（select sorting）它的基本思想是：第一次从arr[0]arr[n-1]中选取最小值，与arr[1]交换，第三次从arr[2]arr[n-1]中选取最小值，与arr[i-1]交换，…, 第n-1次从arr[n-2]~arr[n-1]中选取最小值，与arr[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列
代码简单示例
public static void selectSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int min = arr[i];
int minIndex = i;
// 遍历
for (int j = i + 1; j < arr.length; j++) {
if (min > arr[j]) { // 说明min不是真的最小值
min = arr[j]; // 重置min
minIndex = j; // 重置minIndex
}
}
// 判断是否需要交换
if (minIndex != i) {
arr[minIndex] = arr[i];
arr[i] = min;
}
}
}
3、插入排序
插入排序的简单介绍
插入排序（Insertion Sorting）的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表
代码实现
public void insertSort(int[] arr) {
/* i 为排序的数据的下标 将第一个作为已经有序的列表 故，无序从 1 开始 遍历所有未排序元素*/
for (int i = 1; i < arr.length; i++) {
/* j 已经排序的下标 */
int j = i - 1;
/* 待排序数据 */
int insertValue = arr[i];
/*如果当前数据与排序后的最后一个数据比较，如果当前数据比插入后的数据小，就将插入后的数据后移动 */
for (; j >= 0 && insertValue < arr[j]; j--) {
/* 将排序后的数据后移一位 */
arr[j + 1] = arr[j];
}
/* 将待插入的数据放到找到的 不满足 （ j >= 0 && arr[j] > arr[i] ） 条件的前一个位置*/
arr[j + 1] = insertValue;
}
}
4、希尔排序
概述
简单插入排序存在的问题:
我们看简单的插入排序可能存在的问题.
数组 arr = {2,3,4,5,6,1} 这时需要插入的数 1(最小), 这样的过程是：
{2,3,4,5,6,6}
{2,3,4,5,5,6}
{2,3,4,4,5,6}
{2,3,3,4,5,6}
{2,2,3,4,5,6}
{1,2,3,4,5,6}
结论: 当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响.
希尔排序法介绍
希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。
基本思想:
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止图示：
代码实现
/**
* 实现代码： 首先分组，之后再进行shell排序即可
* @param arr
*/
public void shellSort(int[] arr) {
/* 分组 ，gap 是 分组后的步长 */
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
/* 进行shell排序 */
/* i 为排序的数据的下标 遍历所有未排序元素*/
for (int i = gap; i < arr.length; i ++) {
/* j 已经排序的下标 */
int j = i - gap;
/* 待排序数据 */
int insertValue = arr[i];
/*如果当前数据与排序后的最后一个数据比较，如果当前数据比插入后的数据小，就将插入后的数据后移动 */
for (; j >= 0 && insertValue < arr[j]; j -= gap) {
/* 将排序后的数据后移一位 */
arr[j + gap] = arr[j];
}
/* 将待插入的数据放到找到的 不满足 （ j >= 0 && arr[j] > arr[i] ） 条件的前一个位置*/
arr[j + gap] = insertValue;
}
}
}
5、快速排序
概述
快速排序（Quicksort）是对冒泡排序的一种改进。
基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
分析：
基本思想:
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。
虽然快速排序称为分治法，但分治法这三个字显然无法很好的概括快速排序的全部步骤。因此对快速排序作了进一步的说明：挖坑填数+分治法
挖坑填数+分治法 分析：
- 以一个数组作为示例，取区间第一个数为基准数。 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- |
| 72 | 6 | 57 | 88 | 60 | 42 | 83 | 73 | 48 | 85 |
- 初始时，i = 0; j = 9; X = a[i] = 72
- 由于已经将 a[0] 中的数保存到 X 中，可以理解成在数组 a[0] 上挖了个坑，可以将其它数据填充到这来。
- 从j开始向前找一个比X小或等于X的数。当j=8，符合条件，将a[8]挖出再填到上一个坑a[0]中。a[0]=a[8]; i++; 这样一个坑a[0]就被搞定了，但又形成了一个新坑a[8]，这怎么办了？简单，再找数字来填a[8]这个坑。这次从i开始向后找一个大于X的数，当i=3，符合条件，将a[3]挖出再填到上一个坑中a[8]=a[3]; j—;
数组变为：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- |
| 48 | 6 | 57 | 88 | 60 | 42 | 83 | 73 | 88 | 85 |
- i = 3; j = 7; X=72
- 再重复上面的步骤，先从后向前找，再从前向后找。
- 从j开始向前找，当j=5，符合条件，将a[5]挖出填到上一个坑中，a[3] = a[5]; i++;
- 从i开始向后找，当i=5时，由于i==j退出。
- 此时，i = j = 5，而a[5]刚好又是上次挖的坑，因此将X填入a[5]。
数组变为：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- |
| 48 | 6 | 57 | 42 | 60 | 72 | 83 | 73 | 88 | 85 |
- 1．i =L; j = R; 将基准数挖出形成第一个坑a[i]。
- 2．j—由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
- 3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。
实现挖坑填数的代码
``` //快速排序 void quickSort(int s[], int l, int r) {
if (l < r) { //将中间的这个数和第一个数交换 int i = l, j = r, x = s[l]; while (i < j) { while (i < j && s[j] >= x) { // 从右向左找第一个小于x的数 j--; } if (i < j) { s[i++] = s[j]; } while (i < j && s[i] < x) { // 从左向右找第一个大于等于x的数 i++; } if (i < j) { s[j--] = s[i]; } } s[i] = x; // 递归调用 quick_sort(s, l, i - 1); quick_sort(s, i + 1, r); }}
## 6、归并排序
### 简介
> 归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
> 归并排序思想示意图1-基本思想
> <br />
归并排序思想示意图2-合并相邻有序子序列:
> <br />
### 代码实现
//归并排序
public static void mergeSort(int[] arr,int low,int high) { int middle=(high+low)/2; if(low<high) { //处理左边 mergeSort(arr, low, middle); //处理右边 mergeSort(arr, middle+1, high); //归并 merge(arr,low,middle,high); } }
/**
- 合并数组前后两部分 *
- @param arr 数组
- @param low 开始位置
- @param middle 中间分割位置
- @param high 结束位置
*/
public static void merge(int[] arr,int low,int middle, int high) {
//用于存储归并后的临时数组
int[] temp = new int[high-low+1];
//记录第一个数组中需要遍历的下标
int i=low;
//记录第二个数组中需要遍历的下标
int j=middle+1;
//用于记录在临时数组中存放的下标
int index=0;
//遍历两个数组取出小的数字，放入临时数组中
while(i<=middle&&j<=high) {
} //处理多余的数据 while(j<=high) {//第一个数组的数据更小 if(arr[i]<=arr[j]) { //把小的数据放入临时数组中 temp[index]=arr[i]; //让下标向后移一位； i++; }else { temp[index]=arr[j]; j++; } index++;
} while(i<=middle) {temp[index]=arr[j]; j++; index++;
} //把临时数组中的数据重新存入原数组 for(int k=0;k<temp.length;k++) {temp[index]=arr[i]; i++; index++;
} }arr[k+low]=temp[k];
## 7、归并排序
### 基数排序(桶排序)介绍
> 基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用
> 基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法<br />
基数排序(Radix Sort)是桶排序的扩展
> 基数排序是1887年赫尔曼·何乐礼发明的。它是这样实现的：将整数按位数切割成不同的数字，然后按每个位数分别比较。
### 基数排序基本思想
> 将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
> 基数排序图文说明:
>
> 将数组 {53, 3, 542, 748, 14, 214} 使用基数排序, 进行升序排序:
>
> 第1轮排序 [按照个位排序]:<br />
说明： 事先准备10个数组(10个桶)， 0-9 分别对应 位数的 0-9<br />
(1) 将 各个数，按照个位大小 放入到 对应的 各个数组中<br />
(2) 然后从 0-9 个数组/桶，依次，按照加入元素的先后顺序取出<br />
> 第1轮排序后：{542, 53 ,3 ,14 ,214 ,748}
>
> 第2轮排序 [按照十位排序]
> (1) 将 各个数，按照十位大小 放入到 对应的 各个数组中<br />
(2) 然后从 0-9 个数组/桶，依次，按照加入元素的先后顺序取出<br />
<br />
第2轮排序后： {3 ,14 ,214 ,542 ,748 ,53}
>
> 第3轮排序 [按照百位排序]<br />
(1) 将 各个数，按照百位大小 放入到 对应的 各个数组中<br />
(2) 然后从 0-9 个数组/桶，依次，按照加入元素的先后顺序取出<br />
<br />
第3轮排序后：{3 ,14 ,53 ,214 ,542 ,748} 【ok】
### 代码实现
public static void radixSort(int[] arr) {
//存最数组中最大的数字
int max=Integer.MIN_VALUE;
for(int i=0;i<arr.length;i++) {
if(arr[i]>max) {
max=arr[i];
}
}
//计算最大数字是几位数
int maxLength = (max+"").length();
//用于临时存储数据的数组
int[][] temp = new int[10][arr.length];
//用于记录在temp中相应的数组中存放的数字的数量
int[] counts = new int[10];
//根据最大长度的数决定比较的次数
for(int i=0,n=1;i<maxLength;i++,n*=10) {
//把每一个数字分别计算余数
for(int j=0;j<arr.length;j++) {
//计算余数
int ys = arr[j]/n%10;
//把当前遍历的数据放入指定的数组中
temp[ys][counts[ys]] = arr[j];
//记录数量
counts[ys]++;
}
//记录取的元素需要放的位置
int index=0;
//把数字取出来
for(int k=0;k<counts.length;k++) {
//记录数量的数组中当前余数记录的数量不为0
if(counts[k]!=0) {
//循环取出元素
for(int l=0;l<counts[k];l++) {
//取出元素
arr[index] = temp[k][l];
//记录下一个位置
index++;
}
//把数量置为0
counts[k]=0;
}
}
}
}
```
常用排序算法总结和对比
常用排序算法对比
相关术语解释
稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
内排序：所有排序操作都在内存中完成；
外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；时间复杂度： 一个算法执行所耗费的时间。
空间复杂度：运行完一个程序所需内存的大小。
n: 数据规模
k: “桶”的个数
In-place: 不占用额外内存
Out-place: 占用额外内存
若有收获，就点个赞吧
0 人点赞
