大佬教程收集整理的这篇文章主要介绍了【Java数据结构】想进大厂必须牢记于心的——常见八大排序算法，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
📢博客主页：🏀敲代码的布莱恩特🏀 📢欢迎点赞 👍 收藏 ⭐留言 📝 欢迎讨论！👏 📢本文由 【敲代码的布莱恩特】 原创c;首发于 CSDN🙉🙉🙉 📢由于博主是在学小白一枚c;难免会有错误c;有任何问题欢迎评论区留言指出c;感激不尽！✨ 📖精品专栏（不定时更新）【JavaSE】 【Java数据结构】【LeetCode】
递增或递减的排列起来的操作。两个相等的数据c;如果经过排序后c;排序算法能 保证其相对位置不发生变化 c;则我们称该算法是具备 稳定性 的排序算法。
思路：
除了第一个元素之外的所有元素c;内层循环对 当前元素前面有序表进行待插入位置查找c;并进行移动图解：
代码实现：
/**
* 时间复杂度：
* 最好：O(N) -> 数据是有序的
*
* 最坏：O(N^2) -> 无序的数据
*
* 空间复杂度：O(1)
* 稳定性：稳定排序
* @param array
*/
//插入排序
public static void insertSort (int[]array){
for (int i = 1; i<array.length; i++){//外循环
//从1开始表示：假设array[0] 已经放好位置了
//后面的数字就是插入到它左边还是右边的问题。
int tmp = array[i];//设置一个缓存tmp
int j = i-1;
for (; j >=0 ; j--){//内循环
if (array[j]>tmp){//如果arraY[j]大于缓存值c;说明要换位置
array[j+1] = array[j];
}else{//否则直接退出当前这一次的循环
break;
}
}
//最后记得要把缓存值插入到表中
array[j+1] = tmp;//j此时有可能已经是-1了c;所以要变成0下标就得+1
}
}
思路：
所有距离为gap的记录分在同一组内c;并对每一组内的记录进行排序。然后c;取gap / 2c;重复上述分组和排序的工作。当gap到达1时c;所有记录在同一组内排好序。
当gap == 1时c;数组已经接近有序的了c;这时 相当于直接用插入排序c;这样就会很快c;因为 直接插入排序是越有序越快。这样整体而言c;可以达到优化的效果。我们实现后可以进行性能测试的对比。图解：
代码实现：
/**
* @param array 排序的数组
* @param gap 每组的间隔 -》 组数
*/
public static void sHell(int[] array,int gap) {
//如果将gap全部换成1c;会发现其实就是直接插入排序
//所以当gap到1的时候c;这就表示这是最后一次排序
//这最后一次排序其实就是一个直接插入排序
for (int i = gap; i < array.length; i++) {
int tmp = array[i];
int j = i-gap;
for (; j >= 0; j -= gap) {
if(array[j] > tmp) {
array[j+gap] = array[j];
}else {
break;
}
}
array[j+gap] = tmp;
}
}
/**
* 时间复杂度：不好算 n^1.3 - n^1.5 之间
* 空间复杂度：O(1)
* 稳定性：不稳定的排序
* 技巧：如果在比较的过程当中 没有发生跳跃式的交换 那么就是稳定的
* @param array
*/
public static void sHellSort(int[] array) {
//处理gap
int gap = array.length;
while (gap > 1) {
gap /= 2;//保证最后一个序列间隔是 1 除几都行
sHell(array,gap);
}
}
思路： 将一组数据分为有序区（排过序的数据）和无序区（未排序数据）c;每一次从无序区间选出最大（或最小）的一个元素c;存放在无序区间的最后（或最前）c;直到全部待排序的数据元素排完 。
选择排序的步骤： 1>首先在未排序序列中找到最小（大）元素c;存放到排序序列的起始位置。 2>再从剩余未排序元素中继续寻找最小（大）元素c;然后放到未排序序列的起始位置。 3>重复第二步c;直到所有元素均排序完毕。
图解：
/**
* 时间复杂度：
* 最好：O(N^2)
* 最坏：O(N^2)
* 空间复杂度：O(1)
* 稳定性：不稳定的
* @param array
*/
public static void SELEctSort(int[] array) {
for (int i = 0; i < array.length; i++) {//下标i前边的为有序区间
for (int j = i+1; j < array.length; j++) {
if(array[j] < array[i]) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
}
}
思路：
准备知识： 堆的结构可以分为大根堆和小根堆c;是一个 完全二叉树c;而堆排序是根据堆的这种数据结构设计的一种排序c;下面先来看看什么是大根堆和小根堆
性质： 每个结点的值都大于其左孩子和右孩子结点的值c;称之为大根堆； 每个结点的值都小于其左孩子和右孩子结点的值c;称之为小根堆。 如下图 
基本步骤：
整个数组的最大值就是堆结构的顶端图解： 
代码实现：
//堆的向下调整
public static void siftDown(int[] array,int root,int len) {//len表示末尾元素下标
int parent = root;
int child = 2*parent+1;//先找到左孩子节点
while (child <= len) {//当child>length的时候说明当前子树已经调整好了
//先根据左孩子节点判断右孩子节点是否存在c;且是否大于左孩子节点
if(child+1 <= len && array[child] < array[child+1]) {//如果存在,且值大于左孩子节点
child++;
}
//child的下标就是左右孩子的最大值下标
if(array[child] > array[parent]) {//如果孩子节点最大值c;大于父节点c;则要交换位置c;因为要建大根堆
int tmp = array[child];
array[child] = array[parent];
array[parent] = tmp;
//继续向下看是否符合大根堆的条件
parent = child;//更新parent下标
child = 2*parent+1;//更新child下标
}else {//否则不用换位置
break;
}
}
}
//建堆
public static void createHeap(int[] array) {
//从小到大排序 -》 大根堆
for (int i = (array.length-1 - 1) / 2; i >= 0 ; i--) {
siftDown(array,i,array.length-1);
}
}
/**
* 时间复杂度：O(N*logN) 都是这个时间复杂度
* 复杂度：O(1)
* 稳定性：不稳定的排序
* @param array
*/
public static void heapSort(int[] array) {
createHeap(array);//O(n)
int end = array.length-1;//end表示当前末尾元素的下标
while (end > 0) {//O(N*logN)
int tmp = array[end];//因为要交换末尾与堆顶元素c;所以先缓存末尾元素
//已经建好堆了c;这时堆顶（0下标元素）就是当前的最大值
array[end] = array[0];//将他提取出来c;放到数组的末尾c;固定住
array[0] = tmp;//将末尾元素换到堆顶
end--;//固定了一个当前堆中的最大值之后c;下一次参与排序的元素就得减少一个
siftDown(array,0,end);//将剩余元素继续变成一个大根堆
}
}
思路：
相邻的两个元素。如果第一个比第二个大则交换他们的位置(升序排列c;降序则反过来)。依次对每一对相邻元素都进行比较。这样c;值最大的元素就通过交换“冒泡”到了列表的结尾c;完成第一轮“冒泡”。每轮比较会有一个元素“冒泡”成功。每轮需要比较的元素个数会递减c;一直到只剩一个元素没有“冒泡”时(没有任何一对元素需要比较)c;则列表排序完成。图解：
/**
* 时间复杂度：
* 最好最坏都是O(n^2) 但是：如果优化了 c;有序的时候就是O(n)
* 空间复杂度：O(1)
* 稳定性：稳定的排序
* 冒泡 直接插入
* @param array
*/
public static void bubbleSort(int[] array) {
for (int i = 0 ;i < array.length-1; i++){//外循环只用length-1趟
Boolean flg = false;//记录当前这一趟是否有换位子
for (int j = 0 ; j <array.length-1-i ; j++){//内循环array.length-1-i趟
if (array[j] > array[j+1]){
int tmp = array[j];
array[j] = array[j+1];
array[j+1] = tmp;
flg = true;
}
}
if (flg==false) {//如果当前趟没换位置c;说明已经有序c;不需要再排序了
break;
}
}
}
思路： 快速排序使用 分治策略 来把一个序列（list）分为两个子序列（sub-lists）。步骤为：
基准"（pivot）。 ①选择边上（左或者右）默认用这种方式 ②随机选择 ③几数取中（例如三数取中）：arraY[left], arraY[R_978_11845@id], arraY[right] 大小是中间的为基准值中间位置。这个称为分区（partition）操作。递归到最底部时c;数列的大小是零或一c;也就是已经排序好了。这个算法一定会结束c;因为在每次的迭代（iteration）中c;它至少会把一个元素摆到它最后的位置去。图解：
代码实现：
/**
* 时间复杂度：
* 最好：O(n*logn) 均匀的分割下
* 最坏：o(n^2) 数据有序的时候
* 空间复杂度：
* 最好：logn
* 最坏：O(n)
* 稳定性：不稳定的排序
*
* k*n*logn
* 2
* 1.2
* @param array
*/
public static void quickSort(int[] array) {
sort(array, 0, array.length - 1);
System.out.println(Arrays.toString(array));
}
private static void sort(int[] array, int low, int high) {
int i = low;
int j = high;
if (array.length <= 1) {
return;
}
if (i >= j) {
return;
}
int pivot = array[i];
while (i < j) {
while (i < j && array[j] >= pivot){
j--;
}
array[i++] = array[j];
while (i < j && array[i] <= pivot){
i++;
}
array[j--] = array[i];
}
array[i] = pivot;//i下标值就是pivot基准值c;由此可以递归左右两边的序列
sort(a, low, i - 1);
sort(a, i + 1, high);
}
非递归实现快速排序（重点掌握递归实现）
/**
* 非递归实现快速排序
* @param array
*/
public static void quickSort_FDG(int[] array) {
Stack<Integer> stack = new Stack<>();
int start = 0;
int end = array.length-1;
int pivot = partition(array,start,end);
//左边有2个元素及以上
if(pivot > start+1) {
stack.push(0);
stack.push(pivot-1);
}
if(pivot < end-1) {
stack.push(pivot+1);
stack.push(end);
}
while (!stack.empty()) {
end = stack.pop();
start = stack.pop();
pivot = partition(array,start,end);
//左边有2个元素及以上
if(pivot > start+1) {
stack.push(0);
stack.push(pivot-1);
}
if(pivot < end-1) {
stack.push(pivot+1);
stack.push(end);
}
}
}
思路： 归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并c;得到完全有序的序列；即先使每个子序列有序c;再使子序列段间有序。若将两个有序表合并成一个有序表c;称为二路归并。 图解：
分而治之
合并相邻有序子序列 再来看看 “治” 阶段c;我们需要将两个已经有序的子序列合并成一个有序序列c;比如上图中的最后一次合并c;要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列c;合并为最终序列[1,2,3,4,5,6,7,8]c;来看下实现步骤。
代码实现：
public static void @H_196_406@merge(int[] array,int low,int mid,int high) {
int s1 = low;
int e1 = mid;
int s2 = mid+1;
int e2 = high;
int[] tmp = new int[high-low+1];
int k = 0;//代表tmp数组的下标
while (s1 <= e1 && s2 <= e2) {
if(array[s1] <= array[s2]) {
tmp[k++] = array[s1++];
//k++;
//s1++;
}else {
tmp[k++] = array[s2++];
}
}
//有2种情况
while (s1 <= e1){
//说明第2个归并段没有了数据 把第1个归并段剩下的数据 全部拷贝过来
tmp[k++] = array[s1++];
}
while (s2 <= e2) {
//说明第1个归并段没有了数据 把第2个归并段剩下的数据 全部拷贝过来
tmp[k++] = array[s2++];
}
//tmp数组当中 存储的就是当前归并好的数据,现在还需要拷贝到原数组中
//这样的代码是错误的
/*for (int i = 0; i < array.length; i++) {
arraY[i] = tmp[i];
}*/
for (int i = 0; i < tmp.length; i++) {
array[i+low] = tmp[i];//加上对应的lowc;用来处理第二个归并段c;如果是第一个归并段c;low=0
}
}
public static void @H_196_406@mergeSorTinternal(int[] array,int low,int high) {
if(low >= high) {
return;
}
int mid = (low+high) / 2;
@H_196_406@mergeSorTinternal(array,low,@H_845_160@mid);//分解前半段
@H_196_406@mergeSorTinternal(array,@H_845_160@mid+1,high);//分解后半段
//合并的过程
@H_196_406@merge(array,low,@H_845_160@mid,high);
}
/**
* 时间复杂度： O(N*log n)
* 空间复杂度：O(N)
* 稳定性：稳定的
* @param array
*/
public static void @H_196_406@mergeSort(int[] array) {
@H_196_406@mergeSorTinternal(array, 0,array.length-1);
}
非递归实现归并排序（了解即可c;重点掌握递归实现）：
/**
* 非递归实现 归并排序
* @param array
* @param gap
*/
public static void @H_196_406@merge2(int[] array,int gap) {
int[] tmp = new int[array.length];
int k = 0;
int s1 = 0;
int e1 = s1+gap-1;
int s2 = e1+1;
//int e2 = s2+gap-1 >= array.length ? array.length-1 : s2+gap-1;
int e2 = s2+gap-1 < array.length ? s2+gap-1 : array.length-1;
//保证有两个归并段
while (s2 < array.length) {
while (s1 <= e1 && s2 <= e2) {
if(array[s1] <= array[s2]) {
tmp[k++] = array[s1++];
}else {
tmp[k++] = array[s2++];
}
}
while (s1 <= e1) {
tmp[k++] = array[s1++];
}
while (s2 <= e2) {
tmp[k++] = array[s2++];
}
//一组完了 确定新的区间的开始和结束
s1 = e2+1;
e1 = s1+gap-1;
s2 = e1+1;
e2 = s2+gap-1 < array.length ? s2+gap-1 : array.length-1;
}
//e2 > array.length
while (s1 <= array.length-1) {
tmp[k++] = array[s1++];
}
for (int i = 0; i < tmp.length; i++) {
array[i] = tmp[i];
}
}
public static void @H_196_406@mergeSort_FDG(int[] array) {
for (int i = 1; i < array.length; i*=2) {
@H_196_406@merge2(array,i);
}
}
思路：
个位c;然后 排好个位的基础上排十位c;以此类推c;直到遍历最高位 次c;排序结束（仔细理解最后一句话）初始化10个桶(固定的)c;桶下标为0-9把这个数字对应的item放到对应的桶中图解：
public static void radixSort(int[] array) {
ArrayList<ArrayList<Integer>> queue = new ArrayList<>();
for (int i = 0; i <10 ; i++) {
queue.add(new ArrayList<>());// 创建一个基数从0---9 每个数字上都是一个list
}
// 找到最大值c;并判断最大值是几位数
int max = array[0];
for (int i = 1; i < array.length; i++) {
if (@H_845_160@max < array[i]) {
max = array[i];
}
}
int time = 0;
while (@H_845_160@max > 0) {
max /= 10;
time++;
}
for (int i = 0; i < time; i++) {// 循环每一个位数（个位、十位、百位）
for (int j = 0; j < array.length; j++) {// 循环数组c;取每一个值
int x = array[j] % (int) @H_748_1626@math.pow(10, i + 1) / (int) @H_748_1626@math.pow(10, i);
ArrayList<Integer> queue3 = queue.get(x);
queue3.add(array[j]);
queue.set(x, queue3);
}
int count = 0;
for (int k = 0; k < 10; k++) {
while (queue.get(k).size() > 0) {
ArrayList<Integer> queue4 = queue.get(k);
array[count] = queue4.get(0);
queue4.remove(0);
count++;
}
}
}
}
一个稳定的排序c;可以变成不稳定的排序 但是一个不稳定的排序c;不可能变成稳定的排序
🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙 ❤原创不易c;如有错误c;欢迎评论区留言指出c;感激不尽❤ ❤ 如果觉得内容不错c;给个三连不过分吧~ ❤ ❤ 看到会回访~ ❤ 🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙
以上是大佬教程为你收集整理的【Java数据结构】想进大厂必须牢记于心的——常见八大排序算法全部内容，希望文章能够帮你解决【Java数据结构】想进大厂必须牢记于心的——常见八大排序算法所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。