数据结构与算法之排序

龙韬 2020-11-07 21:19:25
算法 数据结构 数据 排序 结构


排序算法:

  1. 内部排序:指将需要处理的所有的数据都加载到内部存储器中进行排序

  2. 外部排序:当数据量过大,无法全部加载到内存中,需要借助外部存储器进行排序

  3. 常见的算法分类:


5.1 冒泡排序

基本思想:通过对待排序从前往后(从下标小的元素开始),依次比较相邻的元素的值,如是发现逆序则交换,使值较大的元素逐渐从前移向后部,像水底的起跑一样。

总结规则:

  1. 一共进行n-1次大循环(数组中有n个元素)
  2. 每一次排序的元素在逐渐的减少
  3. 如果在某次排序的过程中,没有发生一次交换,说明排序已经完成了
public static int[] bubbleSort(int[] arr) {
int temp = 0;
boolean flag = false;
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if(arr[j] > arr[j+1]){
flag = true;
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
if(!flag){
break;
}else {
flag = false;
}
}
return arr;
}

5.2 选择排序

选择排序也是属于内部排序,是从要排序的数据中按照指定的规则挑选出某一元素,再依照规则交换位置达到排序的目的。

选择排序的思想:

  1. 从arr[0]--arr[n-1]中找到最小的数值,然后交换arr[0]和最小值交换位置
  2. 从arr[1]--arr[n-1]中找到最小的数值,然后交换arr[1]和最小值交换位置
  3. ........
  4. 直到所有的数据进行交换完成
// 选择排序,选择数组中的最小的元素与arr[0]进行交换,然后继续在剩下的位置寻找次最小值与arr[1]交换,直到将所有的数据排序完成
public static int[] selectSort(int[] arr){
int temp = 0;
int index = 0;
for (int i = 0; i < arr.length-1; i++) {
index = i; // 初始最小值的索引为i
for (int j = i+1; j < arr.length; j++) {
//如果arr[j]小于arr[index],则j为最小值的索引
if(arr[j] < arr[index]){
index = j;
}
}
// 交换最小值和arr[i]的位置
temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
}
return arr;
}

5.3 插入排序

插入排序属于内部排序法,是对于欲排序的元素以插入的方式寻找该元素的适当位置。

插入排序的思想:把n个待排序的元素看做是一个有序表和无序表,开始时有序表中只含有一个元素,无序表中包含n-1个元素。排序的过程中,每次从无序表中取出第一个元素,把它插入到有序表中的适当位置,使之形成新的有序表。

代码的实现:

/**
* 插入排序,将列表看做一个有序表和一个无序表
* @param arr
* @return
*/
public static int[] insertSort(int[] arr){
int temp = 0;
int index = 0;
for (int i = 1; i < arr.length; i++) {
temp = arr[i];
index = i-1;
// 倒叙判断从i-1到0进行判断,如果出现temp>arr[index],则说明arr[index+1]则为要插入的部分
while (index >= 0 && temp < arr[index]){
arr[index+1] = arr[index]; //依次移动数据
index --;
}
// 在arr[index+1]中插入数据
arr[index+1] = temp;
}
return arr;
}

5.4 希尔排序( 缩小增量排序 )

基本思想: 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

安照一定的步长,将一定数量的数据分为一组。设置每组的数据增量为上一次增量的一半,然后将每组的数据量增加,数组减少,直到只剩下一个数组为止。

希尔排序方法:

  1. 对有序序列插入时采用交换法
  2. 对有序序列插入时采用移动法
 /**
* 希尔交换法
* @param arr
* @return
*/
public static int[] shellSort(int[] arr){
int temp = 0;
int count = 0;
for(int gap = arr.length/2; gap > 0; gap /= 2){
for(int i=gap; i< arr.length; i++){
// 遍历组中的所有数据,gap为步长
for(int j=i-gap; j >= 0; j -= gap){
if(arr[j] > arr[j+gap]){
temp = arr[j];
arr[j] = arr[j+gap];
arr[j+gap] = temp;
}
}
}
}
return arr;
}
// 移动位置(结合插入排序)
public static int[] shellMoveSort(int[] arr){
for(int gap = arr.length/2; gap > 0; gap /= 2){
for(int i=gap; i < arr.length; i++){
int j = i;
int temp = arr[j];
if(arr[j] < arr[j-gap]){
while (j - gap >= 0 && temp < arr[j - gap]){
arr[j] = arr[j-gap];
j -= gap;
}
arr[j] = temp;
}
}
}
return arr;
}

5.5 快速排序

基本思想:通过一次排序将要排序的数据分割成独立的两个部分,其中一部分的所有数据都比另一部分的所有数据都要小,然后按照这种方法对这两个部分数据分布进行快速排序,整个排序部分可以使用递归进行,以此达到整个数据变成有序序列。

img

思路分析:

  1. 假设数组为arr,左侧为left,右侧为right,设置选择的初始位置为
  2. 从左侧开始查找,找到大于等于mid的值为止,从右侧也开始查找,直到找到小于等于mid的值
  3. 直到找到l<r的位置,然后递归进行快速排序。
/**
* 快速排序
*
* @param arr
* @param left
* @param right
* @return
*/
public static int[] quickSort(int[] arr, int left, int right) {
if (left >= right) return null;
// 如果数组中left与right相等或者left大于right,则跳出程序
int l = left;
int r = right;
int mid = arr[(l + r) / 2];
int temp = 0;
while (l < r) {
while (l < r && arr[l] < mid) {
l++;
}
while (r > l && arr[r] > mid) {
r--;
}
if (l >= r) {
break;
}
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
if (arr[l] == mid){
r--;
}
if (arr[r] == mid) {
l++;
}
}
quickSort(arr, left, l - 1);
quickSort(arr, r + 1, right);
return arr;
}

5.6 归并排序

归并排序是利用归并的思想实现的排序方法,该算法采用经典的分治策略(分治法将问题为一些小的问题然后递归求解,而治阶段则将分的阶段得到的各答案“修补”在一起,即分而治之

基本方法:

  1. 首先将数组成分成两个部分,一直拆分直到拆分到每个子数组中只有一个元素
  2. 然后进行合并相同相邻的拆分部分,按照顺序进行合并,直到合并成完整的数组
  3. 使用递归方法完成最好,时间复杂度为O(nlogn)

img

 /**
* 归并排序
* @param arr
* @param left
* @param right
* @return
*/
public static int[] mergeSort(int[] arr, int left, int right){
// 如果left大于right,说明数组中只有1个或者没有数据,则将直接返回空
if(left >= right) return null;
int mid = (left + right)/2;
// 分割
mergeSort(arr, left, mid);
mergeSort(arr, mid+1, right);
int i = left;
int j = mid+1;
int t = 0;
int[] temp = new int[(right - left + 1)];
while (i <= mid && j <= right){
if(arr[i] <= arr[j]){
temp[t] = arr[i];
t ++;
i ++;
}else {
temp[t] = arr[j];
t ++;
j ++;
}
}
// 将剩余的内容填充到temp中
while (i <= mid){
temp[t] = arr[i];
t++;
i++;
}
// 将剩余的right内容填充到temp中
while (j <= right){
temp[t] = arr[j];
t++;
j++;
}
// 将temp数据拷贝到arr中
for(int k=left; k<=right; k++){
arr[k] = temp[k-left];
}
System.out.println("排序后的数据为:" + Arrays.toString(temp));
return arr;
}

5.7 基数排序

  1. 基数排序属于“分配式排序”,又称桶子法,它是通过键值的各个位的值,将要排序的元素分配到某些“桶”中,达到排序的作用
  2. 基数排序属于稳定性的排序,基数排序法的是效率高的稳定性排序法
  3. 基数排序是桶排序的拓展
  4. 基数排序的实现方法:将整数位按照位数切割成不同的数字,然后按照每个位分别比较。

img

实现的方法:

  1. 定义一个二维数组,表示10个桶,每一个桶就是一个一维数组
  2. 为了防止在放入输的时候数据溢出,则每个一维数组(桶),大小定为arr.length
  3. 基数排序就是使用空间换时间的经典算法。
 /**
* 基数排序
* @param arr
* @return
*/
public static int[] radixSort(int[] arr){
int[][] bubble = new int[10][arr.length]; //设置桶的数量,每个桶最多盛放整个数组
// 寻找数组中最大的数
int max = arr[0];
for(int i=1; i<arr.length; i++){
if(arr[i] > max){
max = arr[i];
}
}
int maxLength = (max + "").length();
// 根据数值中最大数据的位数判定需要多少次循环
for (int i = 0; i < maxLength; i++) {
int[] bubbleLength = new int[10]; // 桶的放的数据的量
// 将数据根据个位、十位、百位依次放入桶中
for (int j = 0; j < arr.length; j++) {
int size = arr[j] / (int)Math.pow(10, i) % 10;
bubble[size][bubbleLength[size]] = arr[j];
bubbleLength[size] ++;
}
//依次将数据取出,并放入到原来的数组中
int index = 0;
for(int j=0; j<bubble.length; j++){
if(bubbleLength[j] > 0){
for(int k=0; k<bubbleLength[j]; k++){
arr[index++] = bubble[j][k];
}
}
}
}
return arr;
}
版权声明
本文为[龙韬]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/liulongtao/p/13942339.html

  1. 【计算机网络 12(1),尚学堂马士兵Java视频教程
  2. 【程序猿历程,史上最全的Java面试题集锦在这里
  3. 【程序猿历程(1),Javaweb视频教程百度云
  4. Notes on MySQL 45 lectures (1-7)
  5. [computer network 12 (1), Shang Xuetang Ma soldier java video tutorial
  6. The most complete collection of Java interview questions in history is here
  7. [process of program ape (1), JavaWeb video tutorial, baidu cloud
  8. Notes on MySQL 45 lectures (1-7)
  9. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  10. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  11. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  12. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  13. 【递归,Java传智播客笔记
  14. [recursion, Java intelligence podcast notes
  15. [adhere to painting for 386 days] the beginning of spring of 24 solar terms
  16. K8S系列第八篇(Service、EndPoints以及高可用kubeadm部署)
  17. K8s Series Part 8 (service, endpoints and high availability kubeadm deployment)
  18. 【重识 HTML (3),350道Java面试真题分享
  19. 【重识 HTML (2),Java并发编程必会的多线程你竟然还不会
  20. 【重识 HTML (1),二本Java小菜鸟4面字节跳动被秒成渣渣
  21. [re recognize HTML (3) and share 350 real Java interview questions
  22. [re recognize HTML (2). Multithreading is a must for Java Concurrent Programming. How dare you not
  23. [re recognize HTML (1), two Java rookies' 4-sided bytes beat and become slag in seconds
  24. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  25. RPC 1: how to develop RPC framework from scratch
  26. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  27. RPC 1: how to develop RPC framework from scratch
  28. 一次性捋清楚吧,对乱糟糟的,Spring事务扩展机制
  29. 一文彻底弄懂如何选择抽象类还是接口,连续四年百度Java岗必问面试题
  30. Redis常用命令
  31. 一双拖鞋引发的血案,狂神说Java系列笔记
  32. 一、mysql基础安装
  33. 一位程序员的独白:尽管我一生坎坷,Java框架面试基础
  34. Clear it all at once. For the messy, spring transaction extension mechanism
  35. A thorough understanding of how to choose abstract classes or interfaces, baidu Java post must ask interview questions for four consecutive years
  36. Redis common commands
  37. A pair of slippers triggered the murder, crazy God said java series notes
  38. 1、 MySQL basic installation
  39. Monologue of a programmer: despite my ups and downs in my life, Java framework is the foundation of interview
  40. 【大厂面试】三面三问Spring循环依赖,请一定要把这篇看完(建议收藏)
  41. 一线互联网企业中,springboot入门项目
  42. 一篇文带你入门SSM框架Spring开发,帮你快速拿Offer
  43. 【面试资料】Java全集、微服务、大数据、数据结构与算法、机器学习知识最全总结,283页pdf
  44. 【leetcode刷题】24.数组中重复的数字——Java版
  45. 【leetcode刷题】23.对称二叉树——Java版
  46. 【leetcode刷题】22.二叉树的中序遍历——Java版
  47. 【leetcode刷题】21.三数之和——Java版
  48. 【leetcode刷题】20.最长回文子串——Java版
  49. 【leetcode刷题】19.回文链表——Java版
  50. 【leetcode刷题】18.反转链表——Java版
  51. 【leetcode刷题】17.相交链表——Java&python版
  52. 【leetcode刷题】16.环形链表——Java版
  53. 【leetcode刷题】15.汉明距离——Java版
  54. 【leetcode刷题】14.找到所有数组中消失的数字——Java版
  55. 【leetcode刷题】13.比特位计数——Java版
  56. oracle控制用户权限命令
  57. 三年Java开发,继阿里,鲁班二期Java架构师
  58. Oracle必须要启动的服务
  59. 万字长文!深入剖析HashMap,Java基础笔试题大全带答案
  60. 一问Kafka就心慌?我却凭着这份,图灵学院vip课程百度云