关键词：
文章目录
一、插入排序
1.原理
将整个区间分为两个区间:1.有序区间 2.无序区间,每次将无序区间的第一个元素,在有序区间的合适位置插入.
2.代码实现
public static void insertSort(int[] array)
//有序区间[0,i)
//无序区间[i,array.length)
for(int i = 1; i < array.length;i++)
int v = array[i];//无序区间第一个数
int j = i-1;//有序区间最后一个下标
for(; j >= 0 && array[j] > v;j--)
array[j+1] = array[j];
//如果不交换此时下标在i-1
array[j+1] = v;
时间复杂度为O(N^2) ;空间复杂度为O(1)
稳定性 : 稳定排序; 如果array[j] > v换成array[j] >= v就变成不稳地的了.
特点: 1.数组越短,速度越快
2.数组越接近有序,速度越快
二、希尔排序
1.原理
进阶版本的插入排序,先分组,再针对每个组进行排序,逐渐缩小组的个数,最终整个数组就有序了.
2.代码实现
public static void shellSort(int[] arr)
int gap = arr.length / 2;//将数组分为gap组
while (gap > 1 )
//传入组数和数组,带组数的插入排序
insertSortGap(arr,gap);
gap = gap / 2;
insertSortGap(arr,1);
private static void insertSortGap(int[] arr, int gap)
//[0,i)为已排序区间;[i,arr.length)为未排序区间
for(int i = gap ;i < arr.length;i++)
int v = arr[i];
int cur = i - gap;
for( ; cur >= 0&& arr[cur]> v ;cur -= gap)
arr[cur+gap] = arr[cur];
arr[cur + gap] = v;
时间复杂度为O(N^1.3);空间复杂度为O(1)
时间复杂度最好为O(N),最坏为O(N^2);
特点:插入排序的优化版
稳定性 : 不稳定排序
三、选择排序
1.原理
基于打擂台的方式:选数组首元素为擂主,循环遍历数组剩余元素,如果发现比擂主小的元素,就交换两个数.
遍历完成后让擂主加一,重复前面的动作.
2.代码实现
public static void selectSort(int[] arr)
for(int bound = 0; bound < arr.length; bound++)
//bound 位置元素作为擂主,循环进行比较
//如果打擂成功就和擂主交换
for(int cur = bound + 1 ; cur < arr.length; cur++)
if(arr[bound] > arr[cur])
int tmp = arr[bound];
arr[bound] = arr[cur];
arr[cur] = tmp ;
时间复杂度:O(N^2) ;空间复杂度:O(1);
稳定性 : 不稳定排序
四、堆排序
1.原理
升序排列:将数组建一个大堆,然后将堆顶元素和堆底元素交换,重新生成一个大堆,并且将堆的大小减一,每一次循环
都会让数组的最后一个元素是较大者,重复这个过程就实现了堆排序. 数组就是升序.
2.代码实现
public static void heapSort(int[] arr)
//第一步先将传入的数组创建成一个大堆
createHeap(arr);
//循环将堆顶元素与堆底元素交换,并且调整堆
//当堆中是剩一个元素的时候也就不用循环了,所以少循环一次 -1
for(int i = 0 ;i < arr.length -1 ;i ++)
//交换堆顶和堆底元素
//堆顶下标为0 ;堆底下标为arr.length - i -1
swap(arr , 0 ,arr.length - i -1 );
//交换完成再进行向下调整堆; 让堆的大小每次小 1
shiftDown(arr , arr.length - i -1 , 0 );
private static void shiftDown(int[] arr, int heapLength, int index)
int parent = index;
int child = 2 * parent + 1;
while( child < heapLength)
//判断parent左右子树较大者
if( child + 1 < heapLength && arr[child + 1] > arr[child])
child = child + 1;
//判断孩子是否大于,如果大于交换,否则满足大堆直接break
if( arr[child] > arr[parent])
swap(arr, child ,parent);
else
break;
parent = child;
child = 2 * parent + 1;
private static void createHeap(int[] arr)
int cur = (arr.length - 1 - 1) / 2 ;
for( int i = cur ; i >= 0 ;i--)
shiftDown(arr, arr.length, i);
private static void swap(int[] arr, int i, int j)
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp ;
时间复杂度:O(N*log(N)) ;空间复杂度:O(1);
稳定性 : 不稳定排序
五、冒泡排序
1.原理
升序排列:将一个无序的区间相邻进行比较,较大的放在后面,循环比较,一次循环可以把最大的放在数组最后,下一次
循环可以将较大者放到次后位置,循环N次就得到了一个升序数组.
2.代码实现
public static void bubbleSort(int[] arr)
//循环 i 次
for(int i = 0 ; i < arr.length ;i++)
//每循环一次会确定一个较大值
//注意数组下标越界bound + 1 < arr.length - i
for(int bound = 0 ;bound + 1 < arr.length - i ;bound++)
if(arr[bound + 1] < arr[bound])
int tmp = arr[bound];
arr[bound] = arr[bound + 1];
arr[bound + 1 ] = tmp;
时间复杂度:O(N^2) ;空间复杂度:O(1);
稳定性 : 稳定排序
六、快速排序
1.原理
升序排列:1.在待排数组中选取一个数作为基准值(一般选最左侧或最右侧作为基准值;
2.比基准值大的放在基准值的右边,比基准值小的放在基准值的左边
3.在递归排序基准值的左边,递归基准值的右边
2.代码实现
递归版本
public static void quickSort(int[] arr)
//借助helper方法进行递归
//为了代码简单设置成前闭后闭区间[left,right]
quickSortHelper(arr ,0 ,arr.length - 1);
private static void quickSortHelper(int[] arr, int left, int right)
//判断数组元素有几个,如果有0个或者1个就无需排序,直接return;
if(left >= right)
return ;
//通过partition对数组进行分区左侧为小于基准值,右侧为大于基准值
//index 为整理后left和right重合的位置
int index = partition(arr ,left ,right);
quickSortHelper(arr ,left , index - 1);
quickSortHelper(arr , index + 1,right);
private static int partition(int[] arr, int left, int right)
int i = left ;
int j = right ;
int base = arr[right]; //将数组最后一个元素设为基准值
//left < right 说明数组还没判断完
while( i < j)
while ( i < j && arr[i] <= base)
i++ ;
//循环结束后,要么i和j重回,要么i下标是一个比base值大的数
while ( i < j && arr[j] >= base)
j-- ;
//循环结束要么j和i重合,要么j下标是一个比base小的数
//交换i和j下标的元素
swap(arr,i ,j);
//循环结束要将i或j(i和j此时在同一位置)位置的元素和right(基准值)元素进行交换
swap(arr, i , right);
//返回基准值位置
return i;
private static void swap(int[] arr, int i, int j)
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp ;
时间复杂度:O(N*log(N)) ;空间复杂度:O(log(N))主要是因为递归;
稳定性 : 不稳定排序
非递归版本
public static void quickSortByLoop(int[] arr)
//通过栈来模拟实现递归
Stack<Integer> stack = new Stack<>();
//将数组左右位置下标入栈
stack.push(arr.length - 1);
stack.push(0);
while (!stack.empty())
//出栈顺序和入栈顺序相反
int left = stack.pop();
int right = stack.pop();
//如果左右区间之间只有一个数证明已经有序 直接进行下一次循环
if( left >= right)
continue ;
int index = partition(arr , left ,right);
//排序后的右区间[ index + 1 ,right]
stack.push(right);
stack.push(index + 1);
//排序后的左区间[left ,index - 1]
stack.push(index - 1);
stack.push(left);
private static int partition(int[] arr, int left, int right)
int i = left ;
int j = right ;
int base = arr[right]; //将数组最后一个元素设为基准值
//left < right 说明数组还没判断完
while( i < j)
while ( i < j && arr[i] <= base)
i++ ;
//循环结束后,要么i和j重回,要么i下标是一个比base值大的数
while ( i < j && arr[j] >= base)
j-- ;
//循环结束要么j和i重合,要么j下标是一个比base小的数
//交换i和j下标的元素
swap(arr,i ,j);
//循环结束要将i或j(i和j此时在同一位置)位置的元素和right(基准值)元素进行交换
swap(arr, i , right);
//返回基准值位置
return i;
private static void swap(int[] arr, int i, int j)
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp ;
时间复杂度:O(N*log(N)) ;空间复杂度:O(log(N))
稳定性 : 不稳定排序
七、归并排序
1.原理
升序排列:将数组分成若干个子数组,若子数组仅剩一个元素那么他就是有序的,然后将这些已有的子序列合并,得到
一个有序的数列.而将两个有序表合成一个有序表就是"二路归并".
2.代码实现
递归实现
public static void mergeSort(int[] arr)
//创建一个helper方法帮助完成递归
mergeSortHelper(arr ,0 ,arr.length);
private static void mergeSortHelper(int[] arr, int low, int high)
if( high - low <= 1)
return;
//求出中间值
int mid = (low + high) / 2;
//这个递归执行完 [low,mid)就已经排序好了
mergeSortHelper(arr,low ,mid);
//这个递归执行完[mid,high)就已经排序好了
mergeSortHelper(arr,mid , high);
//对[low, high)进行排序
merge(arr ,low ,mid ,high);
private static void merge(int[] arr, int low, int mid, int high)
int[] output = new int[high - low];
int cur1 = low;
int cur2 = mid;
//记录output数组存放了多少元素
int outputIndex = 0 ;
while (cur1 < mid && cur2 < high)
//这里写成 > 才能保证稳定性
if(arr[cur1] > arr[cur2])
output[outputIndex] = arr[cur2];
outputIndex++;
cur2 ++;
else
output[outputIndex] = arr[cur1];
outputIndex ++;
cur1 ++;
//上面循环结束不是cur1到mid就是cur2到high
//再写两个循环将剩余的元素写入output数组中
while (cur1 < mid)
output[outputIndex] = arr[cur1];
outputIndex ++;
cur1 ++;
while (cur2 < high)
output[outputIndex] = arr[cur2];
outputIndex ++;
cur2 ++;
//将output数组中的元素放回arr数组
for(int i = 0 ;i < high - low ;i ++)
arr[low + i ] = output[ i];
非递归实现
public static void mergeSortByLoop(int[] arr)
//定义一个gap变量进行分组
for (int gap = 1 ; gap < arr.length;gap *= 2)
for(int i = 0 ;i < arr.length ;i = i + 2 * gap)
int low = i ;
int mid = i + gap;
int high = i + 2* gap;
if(mid > arr.length)
mid = arr.length;
if(high > arr.length)
high = arr.length;
merge(arr , low , mid ,high);
private static void merge(int[] arr, int low, int mid, int high)
int[] output = new int[high - low];
int cur1 = low;
int cur2 = mid;
//记录output数组存放了多少元素
int outputIndex = 0 ;
while (cur1 < mid && cur2 < high)
//这里写成 > 才能保证稳定性
if(arr[cur1] > arr[cur2])
output[outputIndex] = arr[cur2];
outputIndex++;
cur2 ++;
else
output[outputIndex] = arr[cur1];
outputIndex ++;
cur1 ++;
//上面循环结束不是cur1到mid就是cur2到high
//再写两个循环将剩余的元素写入output数组中
while (cur1 < mid)
output[outputIndex] = arr[cur1];
outputIndex ++;
cur1 ++;
while (cur2 < high)
output[outputIndex] = arr[cur2];
outputIndex ++;
cur2 ++;
//将output数组中的元素放回arr数组
for(int i = 0 ;i < high - low ;i ++)
arr[low 六千字快速复习七种常用排序(代码片段)
文章目录一、插入排序1.原理2.代码实现二、希尔排序1.原理2.代码实现三、选择排序1.原理2.代码实现四、堆排序1.原理2.代码实现五、冒泡排序1.原理2.代码实现六、快速排序1.原理2.代码实现递归版本非递归版本七、归并排序1.原... 查看详情
基于比较的七种常见排序算法(代码片段)
...归并排序基本思想代码实现优化版自底向上版复杂度分析快速排序基本思想代码实现复杂度分析非递归实现(代码)三路快速排序(代码)前言本文主要介绍基于比较的七种常见排序算法，分别为：选 查看详情
mysql常用的七种join查询(代码片段)
目录一、INNERJION内连接（A∩B ）二、LEFTJOIN左外连接（A全有 ）三、RIGHTJOIN右外连接（B全有）四、FULLJOIN全外连接（A+B） 五、LEFTExcludingJOIN （A-B即A表独有）六、RIGHTExclu 查看详情
快速排序复习(代码片段)
基本思想;类似于归并排序的分治思想,但是在快速排序中会将数组中的元素小的放一边,大的放一边;排序即完成;找切分点,假设数组的第一个元素作为切分点,然后和后面的元素进行比较,只要比当前这个切分点元素小的,就向前交换... 查看详情
[复习]快速排序(代码片段)
原始数组L1，从中任意选择一个基准数F（一般选择第1个），小于F的数据放在F的左边记为数组minList，大于F的数据放在F的右边记为数组maxList。那么L1=minList+F+maxList然后对minList和maxList再做这样的操作，直到minList和maxList中的元素... 查看详情
常用算法(代码片段)
...sp;知识目录一、冒泡排序二、选择排序三、插入排序四、快速排序五、堆排序六、归并排序总结一、冒泡排序1、思路：首先，列表每两个相邻的数比较大小，如果前边的比后边的大，那么这两个数就互换位置。就像是冒泡一样2... 查看详情
分支结构，你会了吗？（五千字超详细教程，带你快速复习）(代码片段)
本章目录每篇前言1.导语2.目标3.知识点1，运算符or表达式 1.1，关系运算符和关系表达式 1.1.1，关系运算符 1.1.2，关系表达式 1.1.3，关系运算实例 1.2，逻辑运算符... 查看详情
拷贝构造，赋值运算符重载（六千字长文详解！）(代码片段)
c++之类和对象详解拷贝构造，赋值运算符重载拷贝构造拷贝构造特征那能不呢使用指针呢？答案是可以的！==因为指针的类型是date产生的临时变量不会引发拷贝构造，但是这时候叫做构造函数，不是拷贝构造函数！==，==因为拷... 查看详情
常见的七种排序算法（java实现）(代码片段)
...法[Java代码]1.冒泡排序2.选择排序3.插入排序4.希尔排序5.快速排序6.归并排序7.基数排序一、算法的一些概念1.排序算法分类排序也称排序算法 查看详情
常见的七种排序算法（java实现）(代码片段)
...法[Java代码]1.冒泡排序2.选择排序3.插入排序4.希尔排序5.快速排序6.归并排序7.基数排序一、算法的一些概念1.排序算法分类排序也称排序算法 查看详情
基于比较的七种常见排序算法(代码片段)
...归并排序基本思想代码实现优化版自底向上版复杂度分析快速排序基本思想代码实现复杂度分析非递归实现(代码)三路快速排序(代码)前言本文主要介绍基于比较的七种常见排序算法，分别为：选择排序法，插入排序... 查看详情
基于比较的七种常见排序算法(代码片段)
...归并排序基本思想代码实现优化版自底向上版复杂度分析快速排序基本思想代码实现复杂度分析非递归实现(代码)三路快速排序(代码)前言本文主要介绍基于比较的七种常见排序算法，分别为：选择排序法，插入排序... 查看详情
算法复习_分治算法之二分搜索棋盘覆盖快速排序(代码片段)
一、基本概念 分治法，顾名思义，即分而治之的算法，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题…… 二、基本思想及策略 设计思想：将一个... 查看详情
2023数据结构考研复习-排序(代码片段)
...排序算法Java版插入排序折半插入排序希尔排序冒泡排序快速排序选择排序堆排序归并排序综合应用题双向冒泡排序算法奇数移动到偶数前面快排枢纽值随机快排找第k小元素荷兰国旗图案2016年真题单链表进行选择排序判断小根堆... 查看详情
算法复习之排序(代码片段)
...STL中多种排序函数：详细解说STL排序二.自己实现排序：1.快速排序:基本思想：定义i,j类似两个哨兵，确定一个基准数分别从要排序数组头尾出发遍历从左到右找大于，从右到左找小于，交换，最后保证大于基准数的在右边，小... 查看详情
mysql常用的七种join查询(代码片段)
目录一、INNERJION内连接（A∩B ）二、LEFTJOIN左外连接（A全有 ）三、RIGHTJOIN右外连接（B全有）四、FULLJOIN全外连接（A+B） 五、LEFTExcludingJOIN （A-B即A表独有）六、RIGHTExcludingJOIN (B-A即... 查看详情
快速排序(代码片段)
...惊闻KaiKai说现在的年轻人连快排都不会写了1.1历史的进程快速排序是由TonyHoare于1959年发明的(前辈要致敬的)那么就会有人问了上个世纪的东西为什么这么厉害呢快速排序真的很快吗？当然这样说说肯定 查看详情
大厂敲门砖，通过动态效果图带你掌握常用算法(代码片段)
...测试六、希尔排序1、基本思想2、效果图3、代码实例七、快速排序1、基本思想2、效果图3、算法描述4、代码实例5、速度测试八、归并排序1、基本思想2、效果图3、代码实现4、速度测试九、基数 查看详情