冒泡排序属于交换排序。效率较低,适用小规模数据集。
原理:循环遍历要排序的元素,依次比较两个相邻的元素,每次循环都找到一个最大(或最小)的数放到最后(或最前)。没有相邻元素需要交换时,说明已经排序完成。
它是稳定排序 (即相等的两个元素,在排序后相对位置不会发生变化)。
- public static void bubbleSort(int[] arrData) {
- int temp;
- int count = 0;
- //控制循环次数
- for (int i = 0; i < arrData.length - 1; ++i) {
- for (int j = 0; j < arrData.length - 1 - i; ++j) {
- ++count;
- if (arrData[j] > arrData[j + 1]) {
- temp = arrData[j];
- arrData[j] = arrData[j + 1];
- arrData[j + 1] = temp;
- }
- }
- }
- System.out.println("比较次数:" + count);
- }
改进算法1,记录本此循环有无数据交换,若无则表示数据已经有序,跳出循环。
- public static void bubbleSort1(int[] arrData) {
- int temp;
- int count = 0;
- boolean noChange;
- //控制循环次数
- for (int i = 0; i < arrData.length - 1; ++i) {
- noChange = true;
- for (int j = 0; j < arrData.length - 1 - i; ++j) {
- ++count;
- if (arrData[j] > arrData[j + 1]) {
- temp = arrData[j];
- arrData[j] = arrData[j + 1];
- arrData[j + 1] = temp;
- noChange = false;
- }
- }
- if (noChange) {
- break;
- }
- }
- System.out.println("比较次数:" + count);
- }
改进算法2,改进算法1加上记录本次循环比较交换的最后位置,后面的元素是有序的,下次循环无需再比较最后位置元素之后的数据。
- public static void bubbleSort2(int[] arrData) {
- int temp;
- int count = 0;
- boolean noChange;
- int lastPos = arrData.length - 1;
- int comparePos = 0;
- //控制循环次数
- for (int i = 0; i < arrData.length - 1; ++i) {
- noChange = true;
- for (int j = 0; j < lastPos; ++j) {
- ++count;
- if (arrData[j] > arrData[j + 1]) {
- temp = arrData[j];
- arrData[j] = arrData[j + 1];
- arrData[j + 1] = temp;
- noChange = false;
- comparePos = j;
- }
- }
- lastPos = comparePos;
- if (noChange) {
- break;
- }
- }
- System.out.println("比较次数:" + count);
- }
对数据{19,25,1,30,12,8,26,24,40,72},bubbleSort的比较次数为45次,bubbleSort1的比较次数为35次,bubbleSort2的比较次数为25次。
快速排序属于交换排序。基于分而治之策略,效率稍高。
原理:每一趟排序将数据分割成左右两部分,其中左边的数据都比右边的数据小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程递归进行,最终整个数据变成有序。
它是不稳定排序 (即相等的两个元素,在排序后相对位置可能发生变化)。
- public static void quickSort(int[] arrData, int left, int right) {
- if (left > right) {
- return;
- }
-
- //基准数
- int base = arrData[left];
- int i = left;
- int j = right;
- while (true) {
- //要先从右向左找
- while (i < j && base <= arrData[j]) {
- --j;
- }
- while (i < j && base >= arrData[i]) {
- ++i;
- }
- if (i >= j) break;
- int temp = arrData[i];
- arrData[i] = arrData[j];
- arrData[j] = temp;
- }
-
- //将基准数和小的数交换
- arrData[left] = arrData[i];
- arrData[i] = base;
-
- //左边排序
- quickSort(arrData, left, i - 1);
- //右边排序
- quickSort(arrData, j + 1, right);
- }
直接插入排序属于插入排序。适合数据个数小于20个的数据集。
原理:将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增1的有序表。一开始有序表就只有第一个数。
- public static void insertSort(int[] arrData) {
- //一开始有序表只有第一个数
- for (int i = 1; i < arrData.length; ++i) {
- //当前数比前一个小
- if (arrData[i] < arrData[i - 1]) {
- int temp = arrData[i];//保存当前数
- int j;
- //查找有序表里的插入位置
- for (j = i - 1; j >= 0 && temp < arrData[j]; --j) {
- arrData[j + 1] = arrData[j];//将前面的大数后移一格
- }
- arrData[j + 1] = temp;
- //System.out.println(Arrays.toString(arrData));
- }
- }
- }
希尔排序属于插入排序,又称“缩小增量排序”,是直接插入排序更高效的改进版本。
原理:把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至 1 时,整个文件恰被分成一组,算法便终止。
- public static void shellSort(int[] arrData) {
- //遍历所有的步长
- for(int d = arrData.length/2; d > 0; d /= 2 ){
- //遍历所有元素
- for(int i = d; i < arrData.length; i++){
- //遍历本组中所有元素
- for(int j = i-d; j >= 0; j -= d){
- //如果当前元素大于加上步长后的那个元素
- if(arrData[j] > arrData[j+d]){
- int temp = arrData[j];
- arrData[j] = arrData[j+d];
- arrData[j+d] = temp;
- }
- }
- }
- }
- }
原理:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。
- public static void selectSort(int[] arrData){
- for(int i=0;i
- int minIndex = i;
- //把当前遍历的数和后面所有数依次进行比较,并记录最小数下标
- for(int j=i+1;j
- if(arrData[minIndex]>arrData[j]){
- minIndex = j;
- }
- }
- //如果最小的数和当前遍历的数下标不一致,说明下标为minIndex的数比当前遍历的数更小
- if(i != minIndex){
- int temp = arrData[i];
- arrData[i] = arrData[minIndex];
- arrData[minIndex] = temp;
- }
- }
- }
6. 归并排序
归并排序是建立在归并操作上的一种有效,稳定的排序算法。
原理:将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。也是基于分而治之策略。
- public static int[] mergeSort(int[] arrData, int low, int high) {
- if (low == high) {
- return new int[]{arrData[low]};
- }
- int mid = low + (high - low) / 2;
- int[] leftArrData = mergeSort(arrData, low, mid); //左有序数组
- int[] rightArrData = mergeSort(arrData, mid + 1, high); //右有序数组
-
- int[] newOut = new int[leftArrData.length + rightArrData.length]; //新有序数组
-
- int m = 0, i = 0, j = 0;
- while (i < leftArrData.length && j < rightArrData.length) {
- newOut[m++] = leftArrData[i] <= rightArrData[j] ? leftArrData[i++] : rightArrData[j++];
- }
- while (i < leftArrData.length)
- newOut[m++] = leftArrData[i++];
- while (j < rightArrData.length)
- newOut[m++] = rightArrData[j++];
- return newOut;
- }
7. 桶排序
桶排序(箱排序)是一种分布式排序。
原理:将数据转换为另一种形式排序。通常用数组来表示每个桶,用原数据的值表示桶的索引。是一种空间换时间的算法。
- public static void bucketSort(int[] arrdata) {
- //注意数据需都>=0
- int max = getMaxOne(arrdata);
- int[] bucket = new int[max + 1];
- for (int i = 0; i < arrdata.length; ++i) {
- bucket[arrdata[i]]++;//计数
- }
- int pos = 0;
- for (int i = 0; i < bucket.length; ++i) {
- for (int j = 0; j < bucket[i]; ++j) {//同一个位置可能有几个相同数据值
- arrdata[pos++] = i;//i是原数据值
- }
- }
- }
-
- static int getMaxOne(int[] arrData) {
- int max = arrData[0];
- for (int i = 1; i < arrData.length; ++i) {
- if (arrData[i] > max) {
- max = arrData[i];
- }
- }
- return max;
- }
8. 基数排序
基数排序(radix sort)属于“分布式排序”(distribution sort)。也是用空间换时间的算法。
原理:透过键值的部份信息,将要排序的元素分配至某些“桶”中,以达到排序的作用。如对整数数列排序中,先以个位为key分组,然后合并;再以十位为key分组,合并;以此类推,直到最大数的最高位。
- public static void radixSort(int[] arrData) {
- //d表示最大数字的位数有多少位
- int d = getLen(getMaxOne(arrData));
-
- int k = 0;
- int n = 1; //作除数
- int m = 1; //控制键值排序依据在哪一位,从第一位即个位开始
- int[][] temp = new int[10][arrData.length]; //数组的第一维表示可能的余数0-9
- int[] order = new int[10]; //数组order[i]用来表示该位是i的数的个数
- while (m <= d) {
- //根据余数来分组
- for (int i = 0; i < arrData.length; i++) {
- int lsd = ((arrData[i] / n) % 10);
- temp[lsd][order[lsd]] = arrData[i];
- order[lsd]++;
- }
- //合并分组
- for (int i = 0; i < 10; i++) {
- if (order[i] != 0) {
- for (int j = 0; j < order[i]; j++) {
- arrData[k] = temp[i][j];
- k++;
- }
- }
- order[i] = 0;
- }
- n *= 10;//作除数
- k = 0;
- m++;//位数+1
- }
- }
-
- static int getMaxOne(int[] arrData) {
- int max = arrData[0];
- for (int i = 1; i < arrData.length; ++i) {
- if (arrData[i] > max) {
- max = arrData[i];
- }
- }
- return max;
- }
-
- static int getLen(int v) {
- return (v + "").length();
- }
9. 堆排序
原理:堆排序首先要构造堆结构。堆结构是一个完全二叉树。完全二叉树指的是,若设二叉树的深度为n,除第 n 层外,其它各层 (1~n-1) 的结点数都达到最大个数,第 n 层所有的结点都连续集中在最左边。完整的堆排序经过反复的两个步骤:构造堆结构和堆排序输出(根节点)。
- public static void heapSort(int[] arrData) {
- int size = arrData.length;
- int i;
- //将n个元素建堆
- for (i = size / 2 - 1; i >= 0; i--) {//只需循环非叶节点
- heapCompare(arrData, i, size);
- }
- int k, t;
- for (i = size - 1; i > 0; i--) {
- //根节点为最大值,放到数组后面
- t = arrData[0];
- arrData[0] = arrData[i];
- arrData[i] = t;
- k = 0;
- heapCompare(arrData, k, i);
- }
- }
-
- static void heapCompare(int[] arrData, int i, int total) {
- //i为非叶节点
- int j;
- while (2 * i + 1 < total) {//第i个节点有子树
- j = 2 * i + 1; //左子节点
- if ((j + 1) < total) {//存在右子节点
- if (arrData[j] < arrData[j + 1])//若左边小于右边
- j++;//指向右子节点
- }
- if (arrData[i] < arrData[j]) {//j为 i节点的子节点
- int t = arrData[i]; //交换数据
- arrData[i] = arrData[j];
- arrData[j] = t;
- i = j;//堆被破坏,需重新调整子树
- } else {//堆未破坏,无需调整
- break;
- }
- }
- }
10. 数据比较
稳定? 原地? 最好 最坏 平均 空间 说明 冒泡排序 是 是 O(n) O(n²) O(n²) O(1) 插入排序 是 是 O(n) O(n²) O(n²) O(1) 归并排序 是 否 O(nLogn) O(nLogn) O(nLogn) O(n) 需额外空间 桶排序 是 否 O(n+k) O(n²) O(n²) O(n*k) k为桶总数 基数排序 是 否 O(d(n+r)) O(d(n+r)) O(d(n+r)) O(n+r) d是关键码个数,r为关键码的最大值 快速排序 否 是 O(nLogn) O(n²) O(nLogn) O(Logn) 希尔排序 否 是 O(n) O(n²) O(nLogn) O(1) 选择排序 否 是 O(n²) O(n²) O(n²) O(1) 最低效 堆排序 否 是 O(nLogn) O(nLogn) O(nLogn) O(1)
-
相关阅读:
python报错 UnicodeDecodeError
关于“支付测试”相关的测试内容
@Elasticsearch之深度应用及原理剖析--文档搜索机制剖析
11月外贸新规
Web攻防01-ASP应用相关漏洞-HTTP.SYS&IIS短文件&文件解析&ACCESS注入
RecyclerView嵌套布局,导致RecyclerView复用失效 解决
Python-简介
【GAMES101 作业3】渲染小奶牛+使用.obj模型+双线性插值+踩坑总结
Spark【RDD编程(二)RDD编程基础】
【二分】Pythagorean Triples—CF1487D
-
原文地址:https://blog.csdn.net/myepicure/article/details/131854570