十大排序算法
1 冒泡排序
1、思想
冒泡排序思想：
通过对要排序的序列从前往后依次比较，从下标小的元素开始，如果发现是逆序就交换，使得较大的值逐渐从前往后移动到序列后面，较小的值从后往前逐渐慢慢往前调整，就像气泡一样慢慢从水中冒起。
2、代码
package com.aa.sort;
import java.util.Arrays;
/**
* @Description: 冒泡排序。思路：从前往后给相邻的两个数进行比较，大的往后放，小的慢慢的冒泡到前面去。
* @Author: AA
*/
public class BubbleSort {
public static void main(String[] args) {
int[] arr = {
1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
bubbleSort3(arr);
System.out.println(Arrays.toString(arr));
}
/**
* 最基础版本。两层循环从头到位比较。
*
* @param arr
*/
public static void bubbleSort1(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
/**
* 稍微优化版本。外层循环比较过的已经放到最后的大值就不需要再在内层循环了。
*
* @param arr
*/
public static void bubbleSort2(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
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;
}
}
}
}
/**
* 最终优化版本。定义一个变量，表示一趟外层循环下来，是否有交换，如果没有交换，其实数据就已经有序了。后续就无须比较了。
*
* @param arr
*/
public static void bubbleSort3(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
boolean flag = false;//定义个标记变量
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]) {
flag = true;
int temp = arr[j];//这个变量也可以拿到外面去，稍微优化一些，大家知道就行。
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
if (!flag) {
break;
} else {
flag = false;
}
}
}
}
2 选择排序
1、思想
1、选择排序思想1
选择排序思想：
第一次从arr[0]-arr[n-1]中选取最小值，与arr[0]进行交换，
第二次从arr[1]-arr[n-1]中选取最小值，与arr[1]进行交换，
第三次从arr[2]-arr[n-1]中选取最小值，与arr[2]进行交换，
......
第i次从arr[i-1]-arr[n-1]中选取最小值，与arr[i-1]进行交换
依次类推
最后一次
第n-1次从arr[n-2]-arr[n-1]中选取最小值，与arr[n-2]进行交换。
其中n为数组长度，i为0到n-1之间的数
总共比较n-1次，就可以得到有序的数组
2、选择排序思想2
选择排序思想：
第一次从arr[1]-arr[n-1]中选取最小值，与arr[0]进行大小比较，小则交换，
第二次从arr[2]-arr[n-1]中选取最小值，与arr[1]进行大小比较，小则交换，
第三次从arr[3]-arr[n-1]中选取最小值，与arr[2]进行大小比较，小则交换，
......
第i次从arr[i]-arr[n-1]中选取最小值，与arr[i-1]进行大小比较，小则交换，
依次类推
倒数第二次
第n-2次从arr[n-2]-arr[n-1]中选取最小值，与arr[n-3]进行大小比较，小则交换，
最后一次
第n-1次从arr[n-1]-arr[n-1]中选取最小值，这个时候就剩一个最后的值了，与arr[n-2]进行大小比较，小则交换。
其中n为数组长度，i为1到n-1之间的数
外层循环总共比较n-1次，就可以得到有序的数组
3、选择排序思想2
通俗易懂版本思想：
从前往后选择，第一次选取最小值放到第一个位置，第二次选取次小值放到第二个位置，... ，依次类推，直到有序。
做学术要严谨，所以给比较不是特别容易理解的思想1和思想2也列出来了，其实思想1和思想2也是一样的，仔细品品。
2、代码
package com.aa.sort;
import java.util.Arrays;
/**
* @Description: 选择排序。思路：从前往后选择，第一次选取最小值放到第一个位置，第二次选取次小值放到第二个位置，... ，依次类推，直到有序。
* @Author: AA
*/
public class SelectSort {
public static void main(String[] args) {
int[] arr = {
1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
selectSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void selectSort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
for (int i = 0; i < arr.length - 1; i++) {
//定义临时最小值和最小值的下标。
int tempMin = arr[i];
int tempIndex = i;
//内层循环主要就是找最小值和最小值的下标
for (int j = i + 1; j < arr.length; j++) {
if (tempMin > arr[j]) {
tempMin = arr[j];
tempIndex = j;
}
}
//找到最小值位置，给放到前面来
arr[tempIndex] = arr[i];//帮内层循环开始前面的一个元素放到内层循环找到最小值的位置
arr[i] = tempMin;//帮最小值放到前面
}
}
}
3 插入排序
1、思想
插入排序思想
插入排序思想：
帮n个待排序的元素看成为一个有序表和一个无序表，开始的时候有序表中只包含一个元素，无序表中包含有n-1个元素，排序的过程中每次从无序表中取出来第一个元素，把它放到有序表的合适的位置，使得有序表整体上仍然保持有序。
2、代码
package com.aa.sort;
import java.util.Arrays;
/**
* @Description: 插入排序
* @Author: AA
*/
public class InsertSort {
public static void main(String[] args) {
int[] arr = {
1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
insertSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void insertSort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
for (int i = 1; i < arr.length; i++) {
//定义一个要插入的值
int value = arr[i];
//找到要插入位置的索引的上一个位置
int index = i - 1;//先假设在当前元素的前面一个位置
while (index >= 0 && value < arr[index]) {
arr[index + 1] = arr[index];
index--;
}
//上面while停止的时候找到了合适的插入的位置，就给value放到对应的地方就行了
//若是value大于前面所有的要插入的值，直接放到最后的位置就行了，同样这样的场景可以看做是找到合适位置的一种特例，所以下面的一行代码是通用的
arr[index + 1] = value;
}
}
}
4 希尔排序
1、思想
希尔排序是一种特殊的插入排序，它是简单插入排序经过改进之后的一个高效的版本，也称之为缩小增量排序。
希尔排序思想：
希尔排序是帮记录值按照下标的一定增量分组，对每组使用直接插入排序算法进行排序，随着增量逐渐减少，每组包含的元素越来越多，当增量减少到1的时候，整个文件恰好被分成了一组，算法终止。
2、代码
package com.aa.sort;
import java.util.Arrays;
/**
* @Description: 希尔排序
* @Author: AA
*/
public class ShellSort {
public static void main(String[] args) {
int[] arr = {
1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
shellSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void shellSort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
for (int gap = arr.length / 2; gap >= 1; gap = gap / 2) {
for (int i = gap; i < arr.length; i++) {
//遍历各个组中间的所有元素，假如按照main中的样例数据，共计5组，步长是5
for (int j = i - gap; j >= 0; j -= gap) {
//如果当前的元素大于加上步长后面的那个元素，则交换
if (arr[j] > arr[j + gap]) {
int temp = arr[j];
arr[j] = arr[j + gap];
arr[j + gap] = temp;
}
}
}
//System.out.println("步长为：" + gap + "的时候排序后的结果是：" + Arrays.toString(arr));
}
}
}
5 快速排序
1、思想
快速排序是对冒泡排序的一种改进。
快速排序思想：
通过一趟排序给要排序的数据分割成为独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小；
然后再按照这种方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，从而让整个数据有序。
2、代码
package com.aa.sort;
import java.util.Arrays;
/**
* @Description: 快速排序
* @Author: AA
*/
public class QuickSort {
public static void main(String[] args) {
int[] arr = {
1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr, int left, int right) {
if (arr == null || arr.length == 0 || left >= right) {
return;
}
int l = left;
int r = right;
int pivot = arr[l];//定义一个标准轴（基准点）
while (l < r) {
//基准点选择了左边，先处理右边。
while (l < r && arr[r] >= pivot) {
r--;
}
if (l < r) {
arr[l] = arr[r];
}
//再处理右边
while (l < r && arr[l] <= pivot) {
l++;
}
if (l < r) {
arr[r] = arr[l];
}
//经过上面的while和if之后，其实就剩了 l==r 一种场景了
arr[l] = pivot;
}
System.out.println("一次标准轴（基准点）移动之后的数组为： " + Arrays.toString(arr));
//递归调用
quickSort(arr, left, l - 1);
quickSort(arr, l + 1, right);
}
}
6 归并排序
1、思想
归并排序思想：
归并排序是利用归并的思想实现的排序算法，这个算法采用经典的分治（divide and conquer）策略。分治法将问题分（divide）成一些小的问题然后递归进行求解，而治（conquer）的阶段则是将分的阶段得到的答案给合并修补到一起，也即是分而治之。
生活中的哲学：
大事化小
小事化了（归平）
2、代码
package com.aa.sort;
import java.util.Arrays;
/**
* @Description: 归并排序
* @Author: AA
*/
public class MergeSort {
public static void main(String[] args) {
int[] arr = {
1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
int[] temp = new int[arr.length];
mergeSort(arr, 0, arr.length - 1, temp);
System.out.println(Arrays.toString(arr));
}
/**
* 排序方法
*
* @param arr 排序数组
* @param left 左下标。数组开始位置。
* @param right 右下标。数据结束位置。
* @param temp 临时数组，中间对比排序放数据使用。
*/
public static void mergeSort(int[] arr, int left, int right, int[] temp) {
if (arr == null || arr.length == 0) {
return;
}
int mid = (left + right) / 2;
if (left < right) {
//分治之分
//递归调用左边
mergeSort(arr, left, mid, temp);
//递归调用右边
mergeSort(arr, mid + 1, right, temp);
//分治之治
merge(arr, left, mid, right, temp);
}
}
//分治之治
public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
//1、准备一些初始的条件
int l = left;
int r = mid + 1;
int t = 0;//临时数组temp的下标变量
//2、给左右两边数组符合条件的放到temp数组中
while (l <= mid && r <= right) {
if (arr[l] <= arr[r]) {
temp[t] = arr[l];
t++;
l++;
} else {
temp[t] = arr[r];
t++;
r++;
}
}
//3、给左右两边还没有放完的数组元素放到temp数组中
while (l <= mid) {
temp[t] = arr[l];
t++;
l++;
}
while (r <= right) {
temp[t] = arr[r];
t++;
r++;
}
//4、从temp数组中拿回数据进行合并
t = 0;//先给t置为0
int tempLeft = left;
while (tempLeft <= right) {
arr[tempLeft] = temp[t];
t++;
tempLeft++;
}
}
}
7 桶排序
1、思想
桶排序思想：
给数据分到多个桶中，使得各个桶之间有序。各个桶内部的数据之间的顺序自行选择排序算法排序。
2、代码
package com.aa.sort;
import java.util.ArrayList;
import java.util.List;
/**
* @Description: 桶排序
* @Author: AA
*/
public class BucketSort {
public static void main(String[] args) {
//假设数据为下面的数组（注意桶排序主要是思想及应用，代码简单）
int[] arr = {
1, 5, 3, 10, 19, 15, 20, 29, 25, 30, 39, 35, 40, 45, 50, 59, 55, 56};
//这里的数据要在桶的范围内。自己根据实际的情况来分别即可
bucketSort(arr);
}
/**
* 桶排序方法
* @param arr
*/
public static void bucketSort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
//1、初始化6个桶（这个根据实际工作的需求来定）
List[] bucket = new ArrayList[6];
//给每个桶初始化
for (int i = 0; i < bucket.length; i++) {
bucket[i] = new ArrayList<Integer>();
}
//2、定义桶的规则，并给元素放到对应的桶中
for (int i = 0; i < arr.length; i++) {
int index = arr[i] / 10;//index代表桶的位置下标，这里的6个桶，下标分别为0-5
bucket[index].add(arr[i]);
}
//3、整体排序
for (int i = 0; i < bucket.length; i++) {
bucket[i].sort(null);//桶内部的元素之间的排序自行选择排序算法排序
for (int j = 0; j < bucket[i].size(); j++) {
//4、打印输出
System.out.print(bucket[i].get(j) + " ");
}
}
}
}
8 基数排序
1、思想
基数排序思想：
基数排序是桶排序的拓展。
给整数按照位数分成不同的数字，然后按照每个 位数 进行比较。
1、将所有的待比较的数值统一为同样的数组长度，数的位数比较短的在前面补零，让所有的数据的位数都保持一样。
2、从低位开始依次进行排序，先排序低位，再排序高位，依次进行。这样从最低位一直排序到最高位完成之后，数据就有序了。
2、代码
package com.aa.sort;
import java.util.Arrays;
/**
* @Description: 基数排序
* @Author: AA
*/
public class RadixSort {
public static void main(String[] args) {
int[] arr = {
1, 123, 12, 2, 234, 23, 3, 345, 34};
radixSort(arr);
System.out.println(Arrays.toString(arr));
}
/**
* 最基础版本。两层循环从头到位比较。
*
* @param arr
*/
public static int[] radixSort(int[] arr) {
if (arr == null || arr.length == 0) {
return arr;
}
//1、先得到数据中最大的数的位数。找出来最大值，数数有几位就行
int max = arr[0];
for (int a : arr) {
max = max < a ? a : max;
}
int maxLength = (max + "").length();
//基数排序，整出来的基数是0-9
for (int i = 0, m = 1; i < maxLength; i++, m = m * 10) {
int[][] bucket = new int[10][arr.length];
int[] bucketElementCounts = new int[10];
for (int j = 0; j < arr.length; j++) {
//第一次按照个位数放入桶中
int pos = (arr[j] / m) % 10;
bucket[pos][bucketElementCounts[pos]] = arr[j];
bucketElementCounts[pos]++;
}
int num = 0;
//给每次分好桶的数据放回到原来的数组中
for (int[] b1 : bucket) {
for (int b2 : b1) {
if (b2 != 0) {
arr[num++] = b2;
}
}
}
}
return arr;
}
}
9 堆排序
1、思想
堆是具有以下性质的完全二叉树：每个节点的值都大于或等于其左右孩子节点的值，称为大顶堆。注意，在这里并没有要求左右孩子节点的值的大小关系。每个节点的值都小于或等于其左右孩子节点的值，称为小顶堆。
堆排序思想：
1、给要排序的序列构造成为一个大顶堆
2、这个时候，整个序列的最大值就是堆顶的跟节点
3、将其与末尾元素进行交换，这个时候末尾的元素就是最大值
4、然后将剩余的n-1个元素重新构建成为一个大顶堆，这样就会得到n个元素的次小值
依次类推，便能得到一个有序序列。
2、代码
package com.aa.sort;
import java.util.Arrays;
/**
* @Description: 堆排序
* @Author: AA
*/
public class HeapSort {
public static void main(String[] args) {
int[] arr = {
1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
/**
* 最基础版本。两层循环从头到位比较。
*
* @param arr
*/
public static void heapSort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
//调整数据为一个大顶堆
for (int i = arr.length / 2 - 1; i >= 0; i--) {
adjustHeap(arr, i, arr.length);
}
//交换堆顶的最大值和最后一个元素，并再次调整
for (int j = arr.length - 1; j > 0; j--) {
int temp = arr[0];
arr[0] = arr[j];
arr[j] = temp;
adjustHeap(arr, 0, j);
}
}
/**
* 调整数据为一个大顶堆
*
* @param arr 数组
* @param i 非叶子节点
* @param length 数组长度
*/
public static void adjustHeap(int[] arr, int i, int length) {
//要清楚堆的定义，就明白下面这句话了。
for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {
//找到i节点的左右子节点中的值较大的节点
if (k + 1 < length && arr[k] < arr[k + 1]) {
k++;
}
if (arr[k] > arr[i]) {
int temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
i = k;
}
}
}
}
10 计数排序
1、思想
计数排序思想：
计数排序是一种非比较排序，是通过计数的方式来完成排序过程。快于任何比较算法。
2、代码
package com.aa.sort;
import java.util.Arrays;
/**
* @Description: 计数排序
* @Author: AA
*/
public class CountSort {
public static void main(String[] args) {
int[] arr = {
1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
int[] res = countSort(arr);
System.out.println(Arrays.toString(res));
}
public static int[] countSort(int[] arr) {
if (arr == null || arr.length == 0) {
return arr;
}
int[] res = new int[arr.length];
int min = arr[0];
int max = arr[0];
for (int a : arr) {
min = min > a ? a : min;
max = max < a ? a : max;
}
//不建议将计数排序应用于最大值和最小值差距特别大的场景，因为开辟的空间太多了。
int length = max - min + 1;
int[] countArr = new int[length];
//计数数组
for (int i = 0; i < arr.length; i++) {
countArr[arr[i] - min] += 1;
}
//累计数组
for (int i = 1; i < countArr.length; i++) {
countArr[i] = countArr[i] + countArr[i - 1];
}
//结果放到res数组中返回
for (int i = 0; i < arr.length; i++) {
res[--countArr[arr[i] - min]] = arr[i];
}
return res;
}
}
十大排序算法
1、十大排序算法之冒泡排序
2、十大排序算法之选择排序
3、十大排序算法之插入排序
4、十大排序算法之希尔排序
5、十大排序算法之快速排序
6、十大排序算法之归并排序
7、十大排序算法之桶排序
8、十大排序算法之基数排序
9、十大排序算法之堆排序
10、十大排序算法之计数排序
声明：
文章中代码及相关语句为自己根据相应理解编写，文章中出现的相关图片为自己实践中的截图和相关技术对应的图片，若有相关异议，请联系删除。感谢。转载请注明出处，感谢。
By luoyepiaoxue2014
B站： https://space.bilibili.com/1523287361 点击打开链接
微博： http://weibo.com/luoyepiaoxue2014 点击打开链接