八大排序老忘?视图结合高效写出代码(上)!

发布时间:2021-06-12 18:10:43

八大排序老忘?视图结合高效写出代码!
相信很多友友在笔试或者面试的前,如果遇到排序的问题,心中就在想,就是那样那样。可是,一到面对的时候,总是心里一咯噔,沃擦,我怎么说不上来了?本文我会把自己如何快速学*排序的过程分享出来。




文章目录
八大排序老忘?视图结合高效写出代码!1. 选择排序(Selection Sort)1.1 选择排序是什么?1.2 选择排序基本思想1.3 算法描述
2、插入排序(Insertion Sort)2.1 插入排序是什么?2.2 插入排序的基本思想2.3 算法描述
3、冒泡排序(Bubble Sort)3.1 什么是冒泡排序?3.2.冒泡排序的基本思想3.2. 算法描述
4、快速排序(Quick Sort)4.1 什么是快速排序(快排)?4.2 快速排序基本思想4.3 算法实现
总结


八大排序老忘?视图结合高效写出代码(下)!


1. 选择排序(Selection Sort)
1.1 选择排序是什么?

我们先来看一看选择排序的动态演示图:


1.2 选择排序基本思想

选择排序的基本思想是选择+排序
在未排序序列中找到最小(大)元素,存放到未排序序列的起始位置。在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种

1.3 算法描述

根据上图可以观察得:
1.从待排序的序列中,找到最小的元素。
2.如果待排序列第一个元素不是最小的元素,那么就开始往后遍历,找到最小元素,和第一个元素交换位置;
3.从余下的待排序列中(N-1),执行1,2步骤,重复操作,直到结束。
代码实现:


import java.util.Arrays;

public class Demo {
//选择排序
/**
*1.从待排序序列中,找到关键字最小的元素;
* 2.如果最小元素不是待排序序列的第一个元素,将其和第二个元素交换;
* 3.从余下的N-1个元素中,找出关建字最小的元素,重复1.2步骤,直到排序排序结束
* 当增量因子微一时,整个序列长度为原来序列的长度;
*/

public static void main(String[] args) {
int[] arr = {25,89,56,88,21,3,56,66,8,663,55};
Selectionchose(arr);
System.out.println("========================");
int[] res = Selectchose1(arr);
System.out.println(Arrays.toString(res));

}
//展示选择的过程
public static void Selectionchose(int[] arr){
if(arr==null||arr.length==0) return;
//开始遍历,寻找最小的元素,打印出来
for(int i=0;i
int min = i;
for(int j=i+1;j
if(arr[j]
min =j;
}
}
if(min!=i){
int temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
System.out.println(Arrays.toString(arr));
}
}
}
//直接返回最终结果
public static int[] Selectchose1(int[] arr){
if(arr==null||arr.length==0){
System.out.println("序列不合法!");
return null;
}
for(int i =0;i
int min = i;
for(int j =i+1;j
if(arr[min]>arr[j]){
min =j;
}
}
if(min!=i){
int res = arr[i];
arr[i] = arr[min];
arr[min] = res;
}
}
return arr;
}
}



2、插入排序(Insertion Sort)
2.1 插入排序是什么?

我们来看一看插入排序的动态演示图:


2.2 插入排序的基本思想

直接插入排序的基本思想是:将数组中的所有元素依次跟前面已经排好的元素相比较;
如果当前元素的值比之前已经排好的序列中的元素依次比大小,如果比之前序列数小,就直接插入到之前序列数的前面,否则不动;

2.3 算法描述

一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:


①. 从第一个元素开始,该元素可以认为已经被排序
②. 取出下一个元素,在已经排序的元素序列中从后向前扫描
③. 如果该元素(已排序)大于新元素,将该元素移到下一位置
④. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
⑤. 将新元素插入到该位置后
⑥. 重复步骤②~⑤


代码实现:


import java.util.Arrays;

public class Deom {
/**
* 插入排序
*/

public static void main(String[] args) {
int[] arr = {25,89,56,88,21,3,56,66,8,663,55};
//insertionSort(arr);
insertionSort1(arr);
}
//序列较少的情况下:
public static void insertionSort(int[] arr){
if(arr==null||arr.length==0) return;
for(int i =1;i
int temp = arr[i]; //取出第二个元素;
for(int j =i;j>=0;j--){
if(j>0&&arr[j-1]>temp){//j-1为当前元素的前一个元素的下标,如果前一个数大于当前的元素,那么两个数据进行交换
arr[j] = arr[j-1];
System.out.println("inserting"+Arrays.toString(arr));
}else{
arr[j]=temp;//如果大于或等于,那么保存当前数,并且进入下一次插入;
System.out.println("Sorting"+Arrays.toString(arr));
break;
}

}
}
}
//数据量比较多的时候
public static void insertionSort1(int[] arr){
if(arr.length==0||arr==null) return;
for(int i =0;i
for(int j = i+1;j>0;j--){
if(arr[j-1]
break; //如果前一个元素小于当前元素,不做处理
}
int temp = arr[j]; //如果前一个元素大于或等于当前元素时,交换数值,然后进入循环。
arr[j] = arr[j-1];
arr[j-1] = temp;
}
}
System.out.println(Arrays.toString(arr));
}
}



3、冒泡排序(Bubble Sort)


3.1 什么是冒泡排序?

如果你看见过冒泡泡,那么我们可以看见,泡泡在水下向上浮的时候,泡泡的越来越小,及就是大的下沉,小的上浮;



3.2.冒泡排序的基本思想

冒泡排序(Bubble Sort)是一种简单的排序算法。它重复地走访过要排序的数列,
一次比较两个元素,如果他们的顺序错误就把他们交换过来。
走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

3.2. 算法描述

我们先来看一看动态演示图来加深理解;

我们可以看出,大数不断往后移动,小数往前移动。
冒泡排序算法的运作如下:


①. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
②. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
③. 针对所有的元素重复以上的步骤,除了最后一个。
④. 持续每次对越来越少的元素重复上面的步骤①~③,直到没有任何一对数字需要比较。
代码实现:


import java.util.Arrays;

public class Deom {
public static void main(String[] args) {
int[] arr = {25,89,56,88,21,3,56,66,8,663,55};
BubbleSort(arr);
}
public static void BubbleSort(int[] arr){
if(arr.length==0||arr==null) return;
for(int i =0;i //表示第一个元素
for(int j = i+1;j //表示第二个元素
if(arr[i]>=arr[j]){ //如果第一个元素大于等于第二个元素,那么两个元素进行交换,直到不满条件;
int temp = arr[i];
arr[i] =arr[j];
arr[j] = temp;
}
}
}
System.out.println(Arrays.toString(arr));
}
}



4、快速排序(Quick Sort)
4.1 什么是快速排序(快排)?

快速排序(Quicksort)是对冒泡排序的一种改进,借用了分治的思想,由C. A. R. Hoare在1962年提出。


4.2 快速排序基本思想

快速排序的基本思想:挖坑填数+分治法。


首先选一个轴值(pivot,也有叫基准的),通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。
先给出其处理大量数据时的效率图:
单元排序演示:


4.3 算法实现

快速排序使用分治策略来把一个序列(list)分为两个子序列(sub-lists)。步骤为:


①. 从数列中挑出一个元素,称为”基准”(pivot)。
②. 重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
③. 递归地(recursively)把小于基准值元素的子数列和大于基准值元素的子数列排序。


递归到最底部时,数列的大小是零或一,也就是已经排序好了。这个算法一定会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。


代码实现:(递归方法)


import java.util.Arrays;

/**
* 用伪代码描述如下:
*
* ①. i = L; j = R; 将基准数挖出形成第一个坑a[i]。
* ②.j--,由后向前找比它小的数,找到后挖出此数填前一个坑a[i]中。
* ③.i++,由前向后找比它大的数,找到后也挖出此数填到前一个坑a[j]中。
* ④.再重复执行②,③二步,直到i==j,将基准数填入a[i]中
* ????????????????
*
*/

public class Deom {
public static void main(String[] args) {
int[] arr = {25,89,56,88,21,3,56,66,8,663,55};
QuickSort(arr,0,arr.length-1);//以第一个数为基准
}
public static void QuickSort(int[] arr ,int low,int high){
if(arr==null||arr.length==0) return;
if(low>=high) return;
int left = low;
int right = high;
int temp = arr[left]; //确定基准值;
while (left
while (left=temp){ //从后往前,找到小于或等于基准的数进行交换
right--;
}
arr[left] = arr[right];

while (left //从前往后走,找到大于或等于基准的数进行交换
left++;
}
arr[right] = arr[left];
}
arr[left]=temp; //将基准值填到坑3中
//开始递归;
QuickSort(arr,low,left-1);
QuickSort(arr,left+1,high);
System.out.println(Arrays.toString(arr));
}

}


上面是递归版的快速排序:通过把基准temp插入到合适的位置来实现分治,并递归地对分治后的两个划分继续快排。那么非递归版的快排如何实现呢?
因为递归的本质是栈,所以我们非递归实现的过程中,可以借助栈来保存中间变量就可以实现非递归了。在这里中间变量也就是通过QuickSort1函数划分
区间之后分成左右两部分的首尾指针, 只需要保存这两部分的首尾指针即可。

import java.util.Arrays;
import java.util.Stack;

/**
* 用伪代码描述如下:
*
* ①. i = L; j = R; 将基准数挖出形成第一个坑a[i]。
* ②.j--,由后向前找比它小的数,找到后挖出此数填前一个坑a[i]中。
* ③.i++,由前向后找比它大的数,找到后也挖出此数填到前一个坑a[j]中。
* ④.再重复执行②,③二步,直到i==j,将基准数填入a[i]中
* ????????????????
*
*/

public class Deom {
public static void main(String[] args) {
int[] arr = {25,89,56,88,21,3,56,66,8,663,55};
// QuickSort(arr,0,arr.length-1);//以第一个数为基准、
quickSortByStack(arr);
}
public static void QuickSort(int[] arr ,int low,int high){
if(arr==null||arr.length==0) return;
if(low>=high) return;
int left = low;
int right = high;
int temp = arr[left]; //确定基准值;
while (left
while (left=temp){ //从后往前,找到小于或等于基准的数进行交换
right--;
}
arr[left] = arr[right];

while (left //从前往后走,找到大于或等于基准的数进行交换
left++;
}
arr[right] = arr[left];
}
arr[left]=temp; //将基准值填到坑3中
//开始递归;
QuickSort(arr,low,left-1);
QuickSort(arr,left+1,high);
System.out.println(Arrays.toString(arr));
}
/**
* 快速排序(非递归)
*
* ①. 从数列中挑出一个元素,称为"基准"(pivot)。
* ②. 重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
* ③. 把分区之后两个区间的边界(low和high)压入栈保存,并循环①、②步骤
* @param arr 待排序数组
*/
public static void quickSortByStack(int[] arr){
if(arr.length <= 0) return;
Stack stack = new Stack();

//初始状态的左右指针入栈
stack.push(0);
stack.push(arr.length - 1);
while(!stack.isEmpty()){
int high = stack.pop(); //出栈进行划分
int low = stack.pop();
int pivotIdx = QuickSort1(arr, low, high);
//保存中间变量
if(pivotIdx > low) {
stack.push(low);
stack.push(pivotIdx - 1);
}
if(pivotIdx < high && pivotIdx >= 0){
stack.push(pivotIdx + 1);
stack.push(high);
}
}
}

private static int QuickSort1(int[] arr, int low, int high){
if(arr.length <= 0) return -1;
if(low >= high) return -1;
int l = low;
int r = high;

int pivot = arr[l]; //挖坑1:保存基准的值
while(l < r){
while(l < r && arr[r] >= pivot){ //坑2:从后向前找到比基准小的元素,插入到基准位置坑1中
r--;
}
arr[l] = arr[r];
while(l < r && arr[l] <= pivot){ //坑3:从前往后找到比基准大的元素,放到刚才挖的坑2中
l++;
}
arr[r] = arr[l];
}
arr[l] = pivot; //基准值填补到坑3中,准备分治递归快排
System.out.println(Arrays.toString(arr));
return l;
}
}



排序是通常被认为在同数量级(O(nlog2n))的排序方法中*均性能最好的。但若初始序列按关键码有序或基本有序时,快排序反而蜕化为冒泡排序。为改进之,通常以“三者取中法”来选取基准记录,即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。


总结
小胡呕心沥血写了四个排序的图解,太累了,容我再过今天再详细写其他排序算法;排序的时间复杂度和稳定性我会单独写一篇文章,今天我们主要掌握算法,别忘了收藏,转发,评论偶!

相关文档

  • 火锅料的制作菜谱方法
  • 车辆所属权及使用协议书
  • 湛江哪里最好玩哪里有什么好吃的
  • 使用 PHP 开发基于 Web 服务的应用程序
  • 【武器系统】【2013.09】导弹气动参数估计
  • SVM的“三重境界”
  • CAD手机打不图子怎么办
  • 安卓架构MVP(二)
  • 2017时尚吧台装修效果图
  • es和mysql的区别_MySQL用得好好的,为何要转ES?
  • 小米手机蓝牙耳机设置
  • memcache与redis的区别
  • 农村合作医疗保险 农村合作医疗保险一年交多少钱?
  • 酒店优秀员工评选感言参考
  • 初中地理知识学习方法
  • 在沧海中,我是一粒沙
  • 处理国有资产请示范文
  • 华为nova3隐藏应用在哪
  • 微信支付是谁发明的
  • 后端开发三大技术
  • 2020年考研复试英语:开口要讲什么?
  • mysql 5.7.23编译过程及报错。
  • 时代广场的蟋蟀好句好段摘抄大全时代广场的蟋蟀精彩片段
  • 雪初二400字作文
  • cctv健康之路电视什么时间播出
  • 家庭给予我的温暖
  • sonar启动 Process exited with exit value [es]: 143
  • 推动专业社会工作发展的措施
  • 护理求职简历
  • 高三拼搏奋斗的励志教育文章
  • 猜你喜欢

  • 李永强期货训练营视频
  • 语文学习记忆的11种有效的方法技巧
  • 高三百日誓师大会教师的发言稿范文
  • 安徽省滁州市定远县2017-2018学年高一语文下学期开学调研考试试题
  • 仓库进销存表Excel表格
  • 【2019-2020最新】(人教版)初中数学八年级上册教学课件:11.2与三角形有关的角-优质PPT
  • 白银市小学三年级数学上学期开学摸底考试试题 含答案
  • 广西的化妆学校中哪所实力靠谱?
  • 2018-2019年唐山市路北区韩城镇中门庄小学一年级上册语文第一次模拟月考含答案
  • 朝花夕拾西游记知识总结
  • 拉萨市城镇居民信用消费状况影响因素实证分析
  • 2007中国连锁超市大卖场防损状况调查
  • 分娩方式:剖腹产给宝宝带来的6大危害
  • XX年城区环卫综整百日会战实施方案
  • 山东省2015年电工技能鉴定考核考试试卷
  • 优秀残疾人工作者事迹材料1精品资料
  • 黄山市2017-2018学年度第一学期期末质量检测八年级数学试题
  • 永城市华颖商贸有限公司企业信用报告-天眼查
  • 祭扫烈士墓作文600字|祭扫烈士墓有感作文
  • 文后参考文献著录格式示例
  • 【优质文档】九寨沟导游词作文450字-word范文 (2页)
  • 《王安国直言》文言文翻译
  • 那件洁白的球衣
  • 重庆正兴保险代理有限责任公司九龙坡第一分公司企业信用报告-天眼查
  • 【2018-2019】年会演讲稿-word范文模板 (1页)
  • 上海交通大学附属中学-度高二数学第二学期期中试卷
  • 地质岩心钻探吸附卡钻事故的预防与处理
  • 杭州上西家纺有限公司企业信用报告-天眼查
  • 泰州华厦集团公司(泰州市第二建筑安装工程公司)上海第二分公司企业信用报告-天眼查
  • 副教授能带研究生吗
  • 中共党史知识竞赛活动组织工作的通知
  • 关于开展“我身边的共产党员”征文活动的通知
  • 新人教版物理八年级下册:12.1杠杆-练*(2)(含答案).doc
  • 乐视手机进入工程模式
  • 生物必修一细胞分化知识点整理
  • 秋商务星球版地理八上第3章第二节《节约与保护水资源》word教案1
  • 怀孕晚上肚子饿吃什么
  • 2019精选教育专项复*(六) 句子的衔接与排序.ppt
  • 少先队清明节扫墓的活动方案-节日庆典模板
  • 基于Web技术的嵌入式网络视频监控系统研究
  • 现代建筑立面装饰设计的分析
  • 广西的化妆学校中哪所实力靠谱?
  • 电脑版