文档章节

排序思想

o
 osc_gu9d45li
发布于 2019/04/04 23:13
字数 935
阅读 0
收藏 0

精选30+云产品,助力企业轻松上云!>>>

一.几种排序思想

 

1.交换排序:冒泡排序与快速排序

 

冒泡排序:

思想:比较相邻元素,违反排序顺序则交换,每次冒出一个最大值,直到所有相对的最大值冒出,完成排序。

最基本的排序,不必多说。

复杂度:最坏:O(n*n);最好:O(n);O(n*n)。

 

 1 private static void bubblesort(int[] arr) {
 2     for (int i = 0; i < arr.length - 1; i++) { // n-1趟
 3         for (int j = 0; j < arr.length - 1 - i; j++) { // 每趟比n-1-i次
 4             if (arr[j] > arr[j + 1]) {
 5                 int temp = arr[j + 1]; // 交换
 6                 arr[j + 1] = arr[j];
 7                 arr[j] = temp;
 8             }
 9         }
10     }
11 }

 

 快速排序:

思想:

通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,
然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

复杂度:最坏:O(n*n);最好:O(n*logn);平均:O(n*logn)。

 1 private static void quickSort(int[] arr, int start, int end) {
 2         if (start > end)// 出口
 3             return;
 4         
 5         int stard = arr[start];// 将数组的首值设为参照值
 6     
 7         int low = start;// 记录需要排序的下标
 8         int high = end;
 9         
10         while (low < high) {// 循环找出比参照值大和小的数
11             while (low < high && stard <= arr[high]) {// 右边的数比参照大
12                 high--;
13             }            
14             arr[low] = arr[high];// 此时跳出内层循环遇到arr[high]<stard;用右边的数替换左边的数
15             while (low < high && stard >= arr[low]) {// 左边的数比参照小
16                 low++;
17             }
18         arr[high] = arr[low];// 此时arr[low]>atard
19         }    
20         arr[low] = stard;// 将参照赋给low位置的数
21         quickSort(arr, start, low - 1);// 处理所有的小的数字
22         quickSort(arr, low + 1, end);// 处理所有的大的数字
23 
24     }

 

 

1.插入排序:简单插排与希尔排序

简单插排:

思想:

假设待插入元素之前的元素已经是排序完成的,则每一步将一个待排序的元素,按其值的大小插入前面已经排序的序列中适当位置上,直到全部插入完为止。

其中插入具体是指:对于待插入元素temp,如果i位置还不是插入合适的位置,则把i-1位置的元素填到i位置,直到找到合适的位置,或者遍历到0位置,将temp填在i位置。

复杂度:最坏:O(n*n);最好:O(n*n);平均:O(n*n)。

 1 private static void insertSort(int[] arr) {
 2         for (int i = 1; i < arr.length; i++) {// 从第二个元素开始遍历
 3             if (arr[i] < arr[i - 1]) { // 遇到当前元素比前一个元素小的情况
 4                 int temp = arr[i]; // 保存当前元素
 5                 int j;//用于遍历前面所有的情况
 6                 for (j = i - 1; j >= 0 && arr[j] > temp; j--) { // 往前遍历,找到合适的插入位置
 7                     arr[j + 1] = arr[j];
 8                 }
 9                 arr[j + 1] = temp; // 将保存的值存入,即插入到合适的位置,完成排序
10             }
11         }
12     }

 

 

希尔排序:又称缩小增量排序

思想:

按除2递减的步长将序列分组,每组使用直接插排,直到每组都进行插排后完成排序。

复杂度:最坏:O(n*logn*logn);最好:O(n);平均:取决于间隔序列。

 1 private static void shellSort(int[] arr) {
 2         // 遍历步长
 3         for (int step = arr.length / 2; step > 0; step /= 2) {
 4             // 每次进行直接插入排序
 5             for (int i = step; i < arr.length; i += step) {
 6                 if (arr[i] < arr[i - step]) {
 7                     int temp = arr[i];
 8                     int j;
 9                     for (j = i - step; j >= 0 && arr[j] > temp; j -= step) {
10                         arr[j + step] = arr[j];
11                     }
12                     arr[j + step] = temp;
13                 }
14             }
15         }
16     }

 

 

3.

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
十大经典排序算法的python实现

十种常见排序算法可以分为两大类:   非线性时间比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此称为非线性时间比较类排序。包括:冒泡排序、选择排...

翠竹09
2018/09/03
0
0
十大经典排序算法的python实现

十种常见排序算法可以分为两大类:   非线性时间比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此称为非线性时间比较类排序。包括:冒泡排序、选择排...

osc_yny7gjj7
2018/09/03
1
0
Python十大经典排序算法

现在很多的事情都可以用算法来解决,在编程上,算法有着很重要的地位,将算法用函数封装起来,使程序能更好的调用,不需要反复编写。 Python十大经典算法: 一、插入排序 1.算法思想 从第二个...

osc_nhwfplmt
2019/10/02
1
0
7大排序算法

一、排序算法分类 1.外排序:需要在内外存之间多次交换数据 2. 内排序:只在内存中进行 插入排序类 选择排序类 交换类排序类 归并排序类 二、思想与实现 1.插入排序类 直接插入排序 思想:将一...

fenerchen
2018/06/23
0
0
一起学Java(八)-----排序算法

不积跬步,无以至千里;不积小流,无以成江海。 Java语言基础 排序算法 排序的分类: 内排序:待排序列完全存放在内存中进行的排序(这里介绍的都是内排序); 外排序:排序过程需要访问外存...

osc_j6se59id
2019/11/06
2
0

没有更多内容

加载失败,请刷新页面

加载更多

为什么从HBase的0.96版本开始,舍弃了-ROOT-文件?

HBase结构的读写流程 (1). HBase0.96版本之前: (2). HBase0.96开始: a. 当客户端获取到.meta文件的位置之后,会缓存.meta.文件的位置 b. 客户端还会缓存HRegion的位置 -ROOT-存在的意义: ...

其乐m
今天
18
0
volatile关键字对 - What is the volatile keyword useful for

问题: At work today, I came across the volatile keyword in Java. 今天的工作中,我遇到了Java中的volatile关键字。 Not being very familiar with it, I found this explanation: 不太熟......

技术盛宴
今天
25
0
golang 封装 mysql 和 redis 连接

Mysql封装 package dbimport ("fmt"_ "github.com/go-sql-driver/mysql""github.com/jmoiron/sqlx")var DB *sqlx.DBfunc init(){database, err := sqlx.Op......

开源中国最牛的人
今天
21
0
pdfbox 读取文件报错 java.io.IOException: Page tree root must be a dictionary

pdfbox java.io.IOException: Page tree root must be a dictionary 示例代码 public static void main(String[] args) { try (InputStream sampleInputs = new ClassPathResource("s......

lemos
今天
28
0
整理 Linux下列出目录内容的命令

在 Linux 中,有非常多的命令可以让我们用来执行各种各样的任务。当我们想要像使用文件浏览器一样列出一个目录下的内容时,大家第一时间想到的是 ls 命令。但只有 ls 命令能实现这个目的吗?...

良许Linux
今天
17
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部