目录
基本介绍
十大排序算法分为比较类排序和非比较类排序；
比较类排序：通过比较来决定元素之间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也被称为非线性时间比较类排序。
包括插入排序（直接插入排序、希尔排序）、选择排序（直接选择排序、堆排序）、交换排序（冒泡排序、快速排序）、归并排序（二路归并排序、多路归并排序）
非比较类排序：不通过比较来决定元素之间的相对次序，它可以突破基于比较排序的时间下限，以线性时间运行，因此也称为线性时间非比较类排序。
包括计数排序、基数排序、桶排序。
十大排序算法时间复杂度
n ：数据规模
k ：进制数量
d ：最大值的位数
m ：桶的数量
冒泡排序
一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数
列已经排序完成。这个算法的名字由来是因为元素会经由交换慢慢“浮“到数列的顶端。
排序原理
1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个;
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应 该会是最大的数;
3. 针对所有的元素重复以上的步骤，除了最后一个:
4. 重复步骤1~3，直到排序完成
代码实现
public class Bubble {
/**
* 对数组内的元素进行排序
*
* @param a
*/
public static void sort(Comparable[] a) {
//循环的次数取决于需要比较数组的长度
for (int i = a.length - 1; i > 0; i--) {
//从0索引开始，依次和后面的元素比较
//j<i,表示第i个元素的冒泡到了合适位置
for (int j = 0; j < i; j++) {
//如果j处的元素大于j+1处的元素，就换位置
if (greater(a[j], a[j + 1])) {
Bubble.exch(a, j, j + 1);
}
}
}
}
/**
* 判断v是否大于w
*
* @param v
* @param w
* @return
*/
public static boolean greater(Comparable v, Comparable w) {
int result = v.compareTo(w);
return result > 0;
}
/**
* 交换a数组中，索引i和索引j处的值
*
* @param a
* @param i
* @param j
*/
public static void exch(Comparable[] a, int i, int j) {
Comparable temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
测试：
public class BubbleTest {
public static void main(String[] args) {
Integer[] arr = {26,25,35,3,13,39,21,28};
Bubble.sort(arr);
System.out.println("冒泡" + ":" + Arrays.toString(arr));
}
}
选择排序
选择排序的思想其实和冒泡排序有点类似，选择排序可以看成冒泡排序的优化。
排序原理
首先，找到数组中最大(小)的那个元素
其次，将它和数组的第一个元素交换位置(如果第一个元素就是最大(小)元素那么它就和自己交换);
再次，在剩下的元素中找到最大(小)的元素，将它与数组的第二个元素交换位置。如此往
复，直到将整个数组排序。
这种方法叫做选择排序，因为它在不断地选择剩余元素之中的最大(小)者。
代码实现
public class Selection {
/**
* 对数组内的元素进行排序
*
* @param a
*/
public static void sort(Comparable[] a) {
//循环次数取决于需要比较的元素个数
//如果最后剩两个元素还要进行比较，如果只剩下一个，就不要用比较
for (int i = 0; i <= a.length - 2; i++) {
//记录最小元素的索引
int index = i;
for(int j = i+1;j<=a.length-1;j++){
if(greater(a[index],a[j])){
index = j;
}
}
//把最小值给第i个元素
exch(a,i,index);
}
}
/**
* 判断v是否大于w
*
* @param v
* @param w
* @return
*/
public static boolean greater(Comparable v, Comparable w) {
int result = v.compareTo(w);
return result > 0;
}
/**
* 交换a数组中，索引i和索引j处的值
*
* @param a
* @param i
* @param j
*/
public static void exch(Comparable[] a, int i, int j) {
Comparable temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}测试：
public class SelectionTest {
public static void main(String[] args) {
Integer[] arr = {26,25,35,3,13,39,21,28};
Selection.sort(arr);
System.out.println("选择:"+ Arrays.toString(arr));
}
}
插入排序
插入排序是一种简单直观且稳定的排序算法。
排序原理
1. 把所有的元素分为两组，已经排序的和未排序的;
2. 找到未排序的组中的第一个元素，向已经排序的组中进行插入;
3. 倒叙遍历已经排序的元素，依次和待插入的元素进行比较,直到找到一个元素小于等于待插入元素，那么就把待插入元素放到这个位置，其他的元素向后移动一位;
代码实现
public class Insertion {
/**
* 对数组内的元素进行排序
*
* @param a
*/
public static void sort(Comparable[] a) {
//插入排序默认第0个元素已经排好序，直接从第1个元素开始，直到最后一个元素
for (int i = 1;i<a.length;i++){
//将第j个元素之前的元素进行一个倒序遍历
for(int j = i;j>0;j--){
//如果第j-1个元素大于第j个元素，就互换位置，否则进入下一个循环
if(greater(a[j-1],a[j])){
exch(a,j-1,j);
}else {
break;
}
}
}
}
/**
* 判断v是否大于w
*
* @param v
* @param w
* @return
*/
public static boolean greater(Comparable v, Comparable w) {
int result = v.compareTo(w);
return result > 0;
}
/**
* 交换a数组中，索引i和索引j处的值
*
* @param a
* @param i
* @param j
*/
public static void exch(Comparable[] a, int i, int j) {
Comparable temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}测试
public class InsertionTest {
public static void main(String[] args) {
Integer[] arr = {26,25,35,3,13,39,21,28};
Insertion.sort(arr);
System.out.println("插入" + ":" + Arrays.toString(arr));
}
}
快速排序
快速排序是对冒泡排序的一种改进，也是分治法的一个典型应用。
它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
排序原理
1. 首先设定一个分界值，通过该分界值将数组分成左右两部分;
2. 将大于或等于分界值的数据放到到数组右边，小于分界值的数据放到数组的左边。此时左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值;
3. 然后,左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值,将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
4. 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左侧和右侧两个部分的数据排完序后，整个数组的排序也就完成了
代码实现
public class Quick {
//对数组内元素进行排序
public static void sort(Comparable[] a){
int start = 0;
int end = a.length - 1;
sort(a,start,end);
}
//对数组中从索引start到索引end之间的元素进行排序
private static void sort(Comparable[] a,int start,int end){
//安全性校验
if(end <= start){
return;
}
//对a数组进行切分，分成左子组和右子组
int partition = partition(a, start, end);
//让左子组有序
sort(a,start,partition-1);
//让右子组有序
sort(a,partition+1,end);
}
//对数组中从索引start到索引end之间的元素进行分组，返回分组界限对应的索引
public static int partition(Comparable[] a,int start,int end){
//记录分界值
Comparable key = a[start];
//定义两个指针,分别指向待切分数组的最小索引处和最大索引处的下一个位置
int left = start;
int right = end + 1;
while (true){
//先移动右指针，直到找到比分界值小的元素
while (less(key,a[--right])){
if (right == start){
break;
}
}
//再移动左指针，直到找到比分界值大的元素
while (less(a[++left],key)){
if(left == end){
break;
}
}
//判断left是否大于等于right,如果是，说明扫描完成，结束循环，如果不是，交换元素
if (left>=right){
break;
}else {
exch(a,left,right);
}
}
//更新分界值
exch(a,start,right);
return right;
}
//判断v是否小于w
private static boolean less(Comparable v,Comparable w){
int result = v.compareTo(w);
return result < 0;
}
//交换a数组中，索引i和索引j处的值
private static void exch(Comparable[] a,int i,int j){
Comparable temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}测试
public class QuickTest {
public static void main(String[] args) {
Integer[] arr = {26,25,35,3,13,39,21,28};
Quick.sort(arr);
System.out.println("快速" + ":" + Arrays.toString(arr));
}
}
我们可以使用事后分析法对冒泡排序、选择排序和快速性能比较
package linearTest;
import linear.*;
import java.util.ArrayList;
/**
* @Description:
* @ClassName: TestShellAndInsertion
* @Author: 康小汪
* @Date: 2024/1/29 17:29
* @Version: 1.0
*/
public class TestSelectionAndBubble {
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>();
for (int i = 10000;i>=0;i--){
list.add(i);
}
Integer[] a = new Integer[list.size()];
list.toArray(a);
//selection(a);
bubble(a);
//quick(a);
}
public static void bubble(Integer[] a){
//获取执行之前的时间
long start = System.currentTimeMillis();
//执行算法
Bubble.sort(a);
//获取执行之后的时间
long end = System.currentTimeMillis();
//计算执行时间并输出
System.out.println("冒泡排序执行时间:" + (end - start) + "ms");
}
public static void selection(Integer[] a){
//获取执行之前的时间
long start = System.currentTimeMillis();
//执行算法
Selection.sort(a);
//获取执行之后的时间
long end = System.currentTimeMillis();
//计算执行时间并输出
System.out.println("选择排序执行时间:" + (end - start) + "ms");
}
public static void quick(Integer[] a){
//获取执行之前的时间
long start = System.currentTimeMillis();
//执行算法
Quick.sort(a);
//获取执行之后的时间
long end = System.currentTimeMillis();
//计算执行时间并输出
System.out.println("快速排序执行时间:" + (end - start) + "ms");
}
}
希尔排序
希尔排序是插入排序的一种,又称“缩小增量排序”,是插入排序算法的一种更高效的改进版本
排序原理
1. 选定一个增长量h，按照增长量h作为数据分组的依据，对数据进行分组;
2. 对分好组的每一组数据完成插入排序
3. 减小增长量，最小减为1,重复第二步操作。
代码实现
public class Shell {
/**
* 对数组内的元素进行排序
*/
public static void sort(Comparable[] a) {
//先确定增长量h
int h = 1;
while (h < a.length / 2) {
h = 2 * h + 1;
}
//希尔排序
while (h >= 1) {
//确定待排序的元素
for (int i = h; i < a.length; i++) {
//把待排序的元素插入到有序数组中
for (int j = i; j >= h; j -= h) {
if (greater(a[j], a[j - h])) {
//待排序的元素已经在对应的位置了，结束循环
break;
} else {
//交换元素
exch(a, j, j - h);
}
}
}
//减小h
h = h / 2;
}
}
/**
* 判断v是否大于w
*/
public static boolean greater(Comparable v, Comparable w) {
return v.compareTo(w) > 0;
}
/**
* 交换a数组中，索引i和索引j处的值
*/
public static void exch(Comparable[] a, int i, int j) {
Comparable temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}测试
public class ShellTest {
public static void main(String[] args) {
Integer[] arr = {26,25,35,3,13,39,21,28};
Shell.sort(arr);
System.out.println("希尔" + ":" + Arrays.toString(arr));
}
}
我们可以使用事后分析法对希尔排序和插入排序性能比较
public class TestShellAndInsertion {
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>();
for (int i = 100000;i>=0;i--){
list.add(i);
}
Integer[] a = new Integer[list.size()];
list.toArray(a);
//shell(a);
insertion(a);
}
public static void shell(Integer[] a){
//获取执行之前的时间
long start = System.currentTimeMillis();
//执行算法
Shell.sort(a);
//获取执行之后的时间
long end = System.currentTimeMillis();
//计算执行时间并输出
System.out.println("希尔排序执行时间:" + (end - start) + "ms");
}
public static void insertion(Integer[] a){
//获取执行之前的时间
long start = System.currentTimeMillis();
//执行算法
Insertion.sort(a);
//获取执行之后的时间
long end = System.currentTimeMillis();
//计算执行时间并输出
System.out.println("插入排序执行时间:" + (end - start) + "ms");
}
}
归并排序
归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
排序原理
1. 尽可能的一组数据拆分成两个元素相等的子组，并对每一个子组继续拆分，直到拆分后的每个子组的元素个数是1为止。
2. 将相邻的两个子组进行合并成一个有序的大组;
3. 不断的重复步骤2，直到最终只有一个组为止。
代码实现
package linear;
/**
* @Description:
* @ClassName: Quick
* @Author: 康小汪
* @Date: 2024/1/29 16:06
* @Version: 1.0
*/
public class Merge {
//完成归并操作需要的辅助数组
private static Comparable[] assist;
/**
* 对数组内元素进行排序
*/
public static void sort(Comparable[] a) {
//初始化辅助数组assist
assist = new Comparable[a.length];
//定义start和end变量，记录数组中的最小索引和最大索引
int start = 0;
int end = a.length - 1;
//调用sort的重载方法，将数组从start到end索引的元素进行排序
sort(a, start, end);
}
/**
* 对数组中从索引start到索引end之间的元素进行排序
*/
private static void sort(Comparable[] a, int start, int end) {
//安全性校验
if(start >= end ){
return;
}
//对start到end之间的数组进行分组，分成两个组
//定义一个变量，用来确定分组的界限
int mid = start + (end - start) / 2;
//分别对每个组进行排序
sort(a, start, mid);
sort(a, mid + 1, end);
//最后把两个组合并
merge(a, start, mid, end);
}
/**
* 对数组中从索引start到索引mid为一个子组，从索引mid+1到end之间为一个子组，把子组合并成一个有序的大组
*/
public static void merge(Comparable[] a, int start, int mid, int end) {
//定义三个指针
int ass = start;
int p1 = start;
int p2 = mid + 1;
//遍历，移动p1指针和p2指针，比较对应索引处的值，谁小，就把谁放到辅助数组的对应索引处
while (p1 <= mid && p2 <= end) {
if (less(a[p1], a[p2])) {
assist[ass++] = a[p1++];
} else {
assist[ass++] = a[p2++];
}
}
//遍历，如果p1指针没有走完，那么顺序移动p1指针，把对应元素放进辅助数组的对应索引处
while (p1 <= mid) {
assist[ass++] = a[p1++];
}
//遍历，如果p2指针没有走完，那么顺序移动p2指针，把对应元素放进辅助数组的对应索引处
while (p2 <= end) {
assist[ass++] = a[p2++];
}
//把辅助数组中的元素拷贝到原数组中
for (int index = start; index <= end; index++) {
a[index] = assist[index];
}
}
//判断v是否小于w
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
//交换a数组中，索引i和索引j处的值
private static void exch(Comparable[] a, int i, int j) {
Comparable temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
测试
public class MergeTest {
public static void main(String[] args) {
Integer[] arr = {26, 25, 35, 3, 13, 39, 21, 28};
Merge.sort(arr);
System.out.println("归并" + ":" + Arrays.toString(arr));
}
}
堆排序
堆排序是利用堆这种数据结构而设计的一种排序算法，堆具备以下特点
1)完全二叉树;
2)二叉树每个结点的值都大于或等于其左右子树结点的值称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
排序原理
将待排序的序列构造成一个大顶堆，根据大顶堆的性质，当前堆的根节点(堆顶)就是序列中最大的元素，将堆顶元素和最后一个元素交换，然后将剩下的节点重新构造成一个大顶堆，如此反复，从第一次构建大顶堆开始，每一次构建，我们都能获得一个序列的最大值，然后把它放到大顶堆的尾部。最后，就得到一个有序的序列了。
代码实现
package linear;
/**
* @Description:
* @ClassName: Heap
* @Author: 康小汪
* @Date: 2024/1/29 20:08
* @Version: 1.0
*/
public class Heap {
/**
* 对数组内元素进行排序
*/
public static void sort(Comparable[] a) {
//获取数组的长度
int arrLen = a.length;
//初始化一个大顶堆
for (int i = arrLen - 1; i > 0; i--) {
initHeap(a, arrLen);
//将堆顶元素和最后一个元素互换
exch(a, i, 0);
//最后一个元素就是最大值，不在参与计算
arrLen--;
}
}
/**
* 构建大顶堆
*/
public static void initHeap(Comparable[] a, int arrLen) {
//判断最后一个叶子结点有几个孩子
boolean hasTwoChild = (arrLen % 2) == 1 ? true : false;
//从最后一个叶子节点构建大顶堆
for (int i = (arrLen - 2) / 2; i >= 0; i--) {
//如果最后一个叶子节点有两个孩子
if (hasTwoChild) {
//判断它的右孩子是否大于它，并且右孩子是否大于等于左孩子
if (less(a[i], a[(i * 2) + 2]) && less(a[(i * 2) + 1], a[(i * 2) + 2])) {
exch(a, (i * 2) + 2, i);
//交换之后，我们将其调整成大顶堆
downAdjust(a, (i * 2) + 2, arrLen);
}
//判断它的左孩子是否大于它，并且左孩子是否大于等于右孩子
else if (less(a[i], a[(i * 2) + 1]) && less(a[(i * 2) + 2], a[(i * 2) + 1])) {
exch(a, (i * 2) + 1, i);
//交换之后，我们将其调整成大顶堆
downAdjust(a, (i * 2) + 1, arrLen);
}
} else {
if (less(a[i], a[(i * 2) + 1])) {
exch(a, (i * 2) + 1, i);
}
hasTwoChild = true;
}
}
}
/**
* 判断v是否小于w
*/
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
/**
* 交换a数组中，索引i和索引j处的值
*/
private static void exch(Comparable[] a, int i, int j) {
Comparable temp = a[i];
a[i] = a[j];
a[j] = temp;
}
/**
* 调整成大顶堆
*/
private static void downAdjust(Comparable[] a, int i, int arrLen) {
//如果传进来的是叶子结点，直接return
if (i > (arrLen - 2) / 2) {
return;
} else if ((i * 2) + 2 >= arrLen) {
//当只有左孩子时
if (less(a[i], a[(i * 2) + 1])) {
exch(a, (i * 2) + 1, i);
}
} else {
//当只有右孩子时
if (less(a[i], a[(i * 2) + 2]) && less(a[(i * 2) + 1], a[(i * 2) + 2])) {
exch(a, (i * 2) + 2, i);
downAdjust(a, (i * 2) + 2, arrLen);
} else if (less(a[i], a[(i * 2) + 1]) && less(a[(i * 2) + 2], a[(i * 2) + 1])) {
exch(a, (i * 2) + 1, i);
downAdjust(a, (i * 2) + 1, arrLen);
}
}
}
}
测试
public class HeapTest {
public static void main(String[] args) {
Integer[] arr = {26,25,35,3,13,39,21,28};
System.out.println("原数组" + ":" + Arrays.toString(arr));
Heap.sort(arr);
System.out.println("堆排序后" + ":" + Arrays.toString(arr));
}
}
版权声明：本文为博主作者：康小汪原创文章，版权归属原作者，如果侵权，请联系我们删除！
原文链接：https://blog.csdn.net/weixin_52954183/article/details/135909391
