心得技巧
常见的几种排序算法
发布时间：2022-07-02 发布网站：脚本宝典
脚本宝典收集整理的这篇文章主要介绍了常见的几种排序算法，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
目录
一、插入排序
二、 希尔排序
三、选择排序
四、冒泡排序
五、堆排序
六、快速排序
挖坑法
6.1、递归实现
6.2、非递归实现(遍历实现)
七、归并排序
7.1、递归实现
7.2、非递归实现(遍历实现)
一、插入排序
在我看来插入排序就是先将一段数列变得有序，在将后面的数字不断的插入到这个有序数列中来的这种方法叫做插入排序。
步骤：
我们可以把第一个数字看成一个有序数列，从第二个开始循环遍历。在遍历的途中在定义一个循环，不断的与前面的有序数列进行比较，找到位置之后结束本次循环，并将数字插入到有序数列中去，从而达成目的。
代码实现：
public static void insertSort(int[] array) {
for(int i=1;i< array.length;i++){
int j=0;
int temp=array[i];
for(j=i-1;j>=0;j--){
if(temp<array[j]){
array[j+1]=array[j];
}else {
break;
}
}
array[j+1]=temp;
}
}@R_425_1304@：最坏的情况下为O(N^2),此时整个数列接近逆序。最好情况下为O(N),此时整个数列接近有序。
空间复杂度：O(1)；
稳定
插入排序越有序，时间效率越高。
二、 希尔排序
思路：
希尔排序就是一种变相的插入排序，通过不断的变化和调整让希尔排序的时间效率更加的快捷和方便。
步骤：
1.先选定一个小于length的整数key作为第一增量，然后将所有距离为key的元素分在同一组，并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量(我们一般是除2)，重复整个操作。 2.当增量的大小减到1时，就相当于整个序列被分到一组，进行一次直接插入排序，排序完成。
代码实现：
public static void insertSort(int[] array,int val) {
for(int i=val;i< array.length;i++){
int j=0;
int temp=array[i];
for(j=i-val;j>=0;j-=val){
if(temp<array[j]){
array[j+val]=array[j];
}else {
break;
}
}
array[j+val]=temp;
}
}
public static void shellSort(int[] array) {
int key=array.length;
while (key>0){
key=key/2;
insertSort(array,key);
}
}时间复杂度：最坏的情况下为O(N^2)。最好情况下为O(N),此时整个数列接近有序。平均的情况下为O(N^1.3)左右。
空间复杂度：O(1)；
三、选择排序
思路：
选择排序就是确定一个数组的最小值之后将它固定在起始位置，然后继续循环确定，直到完成为止。
代码实现：
public static void selectSort01(int[] array) {
for(int i=0;i<array.length;i++){
for(int j=i+1;j<array.length;j++){
if(array[i]>array[j]){
int temp=array[i];
array[i]=array[j];
array[j]=temp;
}
}
}
}代码优化：
public static void selectSort01(int[] array) {
for(int i=0;i<array.length;i++){
int tmp=i;//把最小的放入tmp中，进行交换
for(int j=i+1;j<array.length;j++){
if(array[tmp]>array[j]){
tmp=j;
}
}
int temp=array[i];
array[i]=array[tmp];
array[tmp]=temp;
}
}时间复杂度：O(N^2)；
空间复杂度：O(1)；
不稳定
四、冒泡排序
思路：
通过比较j和j+1的值来进行交换，将最大的值锁定在最后一个，进行循环。
@H_777_201@
代码实现：
public static void bubbleSort01(int[] array) {
for(int i=0;i<array.length;i++){
for(int j=0;j<array.length-1-i;j++){
if(array[j]>array[j+1]){
int temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
}
}
}
}代码优化：
public static void bubbleSort02(int[] array) {
for(int i=0;i<array.length;i++){
boolean b=false;
for(int j=0;j<array.length-1-i;j++){
if(array[j]>array[j+1]){
int temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
b=true;
}
}
if(b==false){
break;
}
}
}时间复杂度：O(N^2)；
空间复杂度：O(1)；
稳定
五、堆排序
思路：
我们要使用堆排序，那么我们实现要讲数组变成一个大堆，在通过头和尾进行调换、锁定，进行排序，详细的关于堆排序的文章看这个：堆排序。
代码实现：
public static void shiftDown(int[] array,int parent,int len){
int child=parent*2+1;
while (child<len){
if(child+1<len && array[child+1]>array[child]){
child++;
}
if(array[child]>array[parent]){
int temp=array[child];
array[child]=array[parent];
array[parent]=temp;
parent=child;
child=child*2+1;
}else {
break;
}
}
}
public static void createBigHeap(int[] array){
for(int i=(array.length-2)/2;i>=0;i--){
shiftDown(array,i,array.length);
}
}
public static void heapSort(int[] array){
createBigHeap(array);//首先我们要将这个数组变成大堆
int end=array.length-1;
while (end>0){
int temp=array[end];
array[end]=array[0];
array[0]=temp;
shiftDown(array,0,end);
end--;
}
}时间复杂度：O(N*LOGN)；
空间复杂度：O(1)；
不稳定
六、快速排序
挖坑法
对于快速排序我们一般采用挖坑法来解题
6.1、递归实现
思路：
挖坑法就是将队首元素拿出来，从最后一个数向前遍历找到第一个小于队首元素的放入挖的坑中填补，在从前向后遍历找到第一个大于队首元素的放入又挖的坑中填平，重复上述过程。
代码实现：
public static int sort(int[] array,int fast,int end){
int temp=array[fast];
while (fast<end){
while (fast<end && temp<=array[end]){
end--;
}
array[fast]=array[end];
while (fast<end && temp>=array[fast]){
fast++;
}
array[end]=array[fast];
}
array[end]=temp;
return end;
}
public static void asort(int[] array,int left,int right){
if(left>=right){
return;
}
int index=sort(array,left,right);
aSort(array,left,index-1);
aSort(array,index+1,right);
}
public static void qSort(int[] array){
aSort(array,0,array.length-1);
}代码优化：
1.随机选择基准
public static void aSort(int[] array,int left,int right){
if(left>=right){
return;
}
//随机选择
Random rand=new Random();
int arr=rand.nextInt(right-left)+left+1;
int temp=array[left];
array[left]=array[arr];
array[arr]=temp;
int index=sort(array,left,right);
aSort(array,left,index-1);
aSort(array,index+1,right);
}2.三数取中法
public static void find(int[] array,int left,int right){
int mid=(left+right)/2;
//array[mid]<=array[left]<=array[right]
if(array[mid]>array[left]){
int temp=array[mid];
array[mid]=array[left];
array[left]=temp;
}
if(array[left]>array[right]){
int temp=array[right];
array[right]=array[left];
array[left]=temp;
}
if(array[mid]>array[right]){
int temp=array[right];
array[right]=array[mid];
array[mid]=temp;
}
}3.插入排序
//插入排序
if((right-left+1)<=100){
insertSort2(array,left,right);
return;//
}6.2、非递归实现(遍历实现)
思路：
我们可以通过栈先进后出的特性，通过循环来解题。
代码实现：
//快排思想
public static int sort(int[] array,int left,int right){
int temp=array[left];
while (left<right){
while (left<right && temp<=array[right]){
right--;
}
array[left]=array[right];
while (left<right && temp>=array[left]){
left++;
}
array[right]=array[left];
}
array[left]=temp;
return left;
}
public static void quicksort(int[] array){
//我们先创建一个栈
Stack<Integer> stack=new Stack<>();
//先将头和尾放进去
stack.push(0);
stack.push(array.length-1);
int left,right;//创建两个变量对出栈的成员进行赋值
while (!stack.iSEMpty()){
right=stack.pop();
left=stack.pop();
int index=sort(array,left,right);
//进行判断放入其他的元素
//必须要保证有两个或者两个以上的元素才能添加
if(index>left+1){
stack.push(left);
stack.push(index-1);
}
if(index<right-1){
stack.push(index+1);
stack.push(right);
}
}
}时间复杂度：最好O(N*logN)，最坏O(N^2)；
空间复杂度：最好O(logN),最坏O(N);
不稳定
七、归并排序
思想：
我们将数组以二的倍数一步一步进行划分，当划分成一个一个之后进行排序，之后向上排序合并，进行排序。
7.1、递归实现
代码实现：
public static void bSort(int[] array,int left,int mid,int right){
int[] arr=new int[right-left+1];
int k=0;
int as=left;
int ae=;mid;
int ds=mid+1;
int de=right;
while (as<=ae && ds<=de){
if(array[as]<array[ds]){
arr[k++]=array[as++];
}else {
arr[k++]=array[ds++];
}
}
while (as<=ae){
arr[k++]=array[as++];
}
while (ds<=de){
arr[k++]=array[ds++];
}
for(int i=0;i<arr.length;i++){
array[i+left]=arr[i];
}
}
public static void gSort(int[] array,int left,int right){
if(left>=right){
return;
}
//归
int mid=(left+right)/2;
gSort(array,left,mid);
gSort(array,mid+1,right);
//并
bSort(array,left,mid,right);
}
public static void quickSort(int[] array){
gSort(array,0,array.length-1);
}7.2、非递归实现(遍历实现)
代码实现：
public static void gbSort(int[] array,int gay){
int[] arr=new int[array.length];
int k=0;
int as=0;
int ae=as+gay-1;
int bs=ae+1;
int be=bs+gay-1>=array.length-1?array.length-1:bs+gay-1;//需要判断be和array的关系
while (bs<array.length){ //说明至少存在两组
while (as<=ae && bs<=be){
if(array[as]<array[bs]){
arr[k++]=array[as++];
}else{
arr[k++]=array[bs++];
}
}
while (as<=ae){
arr[k++]=array[as++];
}
while (bs<=be){
arr[k++]=array[bs++];
}
as=be+1;
ae=as+gay-1;
bs=ae+1;
be=bs+gay-1>=array.length-1?array.length-1:bs+gay-1;
}
//到这个地方就只有一个
while (as<array.length){
arr[k++]= array[as++];
}
for(int i=0;i<arr.length;i++){
array[i]=arr[i];
}
}
public static void quickSort(int[] array){
for(int i=1;i<array.length;i*=2){
gbSort(array,i);
}
}
时间复杂度：O(N*logN)；
空间复杂度：O(N);
稳定
脚本宝典总结
以上是脚本宝典为你收集整理的常见的几种排序算法全部内容，希望文章能够帮你解决常见的几种排序算法所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。
猜你在找的心得技巧相关文章
- clion结合vcpkg以及GTest的使用 2022-07-07
- EGF 2022-06-06
- ExtJS 布局-Column布局（Column layout） 2022-06-05
- 颜色之ARGB与RGB、RGBA的区别与介绍 2022-04-15
- rgba中的a是什么意思 CSS之RGBA颜色指南 2022-04-15
- rootfs -根文件系统制作 2022-07-07
- 网页简单布局之结构与表现原则分享 2022-04-15
- 小项目中怎么防止Vue的闪现画面效果 2022-04-15
- 隐藏 Web 中的元素方法及优缺点教程详解 2022-04-15
- 告别硬编码让你的前端表格自动计算的实例代码 2022-04-15
全站导航更多
html5HTML/XhtmlCSSXML/XSLTDreamweaver教程Frontpage教程心得技巧JavaScriptASP.NETPHP编程正则表达式AJAX相关ASP编程JSP编程编程10000问CSS/HTMLFlexvbsDOS/BAThtahtcpythonperl游戏相关VBA远程脚本ColdFusionMsSqlMysqlmariadboracleDB2mssql2008mssql2005SQLitePostgreSQLMongoDB星外虚拟主机华众虚拟主机Linuxwin服务器FTP服务器DNS服务器Tomcatnginxzabbix云和虚拟化bios系统安装系统系统进程Windows系列LINUXRedHat/CentosUbuntu/DebianFedoraSolaris红旗Linux建站经验微信营销网站优化网站策划网络赚钱网络创业站长故事alexa域名photoshop教程摄影教程Fireworks教程CorelDraw教程Illustrator教程Painter教程Freehand教程IndesignSketch笔记本主板内存CPU存储显卡显示器光存储鼠标键盘平板电脑安全教程杀毒防毒安全设置病毒查杀脚本攻防入侵防御工具使用业界动态Exploit漏洞分析
最新心得技巧教程