冒泡排序:
public class Bubble {
/**
* @param args
*/
public static void main(String[] args) {
int[] a = { 77, 1, 65, 13, 81, 93, 10, 5, 23, 17 };
for (int m = a.length - 1; m > 0; m--) {
for (int n = 0; n < m; n++) {
if (a[n] > a[n + 1]) {
int temp = a[n];
a[n] = a[n + 1];
a[n + 1] = temp;
}
}
}
for (int i : a) {
System.out.println(i);
}
}
}
复杂度分析:冒泡排序是不稳定的排序算法,一共要比较((n-1)+(n-2)+...+3+2+1)=n*(n-1)/2次,所以时间复杂度是O(n^2)。
快速排序:
public class QuickSort {
/**
* @param args
*/
public static void main(String[] args) {
int[] initArray = { 1, 545, 23, 334, 876, 222, 111, 8, 9, 7, 6, 57, 89,
0, -23, 670 };
qsort(initArray, 0, initArray.length - 1);
outprint(initArray);
}
public static void outprint(int[] initArray) {
for (int i : initArray) {
System.out.println(i);
}
}
public static void swap(int[] array, int a, int b) {
System.out.println("a=" + a);
System.out.println("b=" + b);
int temp = array[b];
array[b] = array[a];
array[a] = temp;
}
public static int getPivotIndex(int[] array, int begin, int end) {
Random r = new Random();
return begin + r.nextInt(end - begin + 1);
}
public static void qsort(int[] array, int begin, int end) {
if (end > begin) {
int index = getPivotIndex(array, begin, end);
index = portions(array, begin, end, index);
qsort(array, begin, index - 1);
qsort(array, index + 1, end);
}
}
public static int portions(int[] array, int begin, int end, int index) {
int pivot = array[index];
swap(array, index, end);
for (int i = index = begin; i < end; i++) {
if (array[i] < pivot) {
swap(array, index++, i);
}
}
swap(array, index, end);
return index;
}
}
最坏情况是和冒泡一样,时间复杂度是O(n^2)
,最好为n*logn 。
插入排序:
public class InsertSort {
/**
* @param args
*/
public static void main(String[] args) {
int[] array = { 77, 1, 65, 13, 81, 93, 10, 5, 23, 17 };
isort(array, 0, array.length);
outprint(array);
}
public static void outprint(int[] initArray) {
for (int i : initArray) {
System.out.println(i);
}
}
public static void swap(int[] array, int a, int b) {
int temp = array[b];
array[b] = array[a];
array[a] = temp;
}
public static void isort(int[] array, int begin, int end) {
for (int i = begin; i < end; i++) {
int temp = array[i];
for (int m = i - 1; m >= 0; m--) {
if (temp < array[m]) {
array[m + 1] = array[m];
array[m] = temp;
} else {
break;
}
}
}
}
}
最好的情况是:顺序已经排好那么我们只要进行n-1次比较即可。
最坏的情况是:顺序恰好是逆序,比较1+2+...+n-1次。
平均时间复杂度也是O(n^2).
分享到:
相关推荐
选择排序、冒泡排序、归并排序、快速排序、插入排序的算法原理。不同排序算法时间效率的经验分析方法,验证理论分析与经验分析的一致性。
java各种排序算法的稳定性和时间复杂度小结
Java数组排序总结(冒泡_选择_插入_希尔)__递归算法的复杂度,实用
在实际应用中,插入排序和现则排序因为实现简单,使用的比较多,但是在对效率要求比较高、且待排序数据量大的场合,还是应该采用时间复杂度较低的排序算法,因此对排序算法进行试验比较,增强实践认识很有必要。...
当我们谈论算法的效率时,时间复杂度是一个关键的概念。它告诉我们随着输入规模增长,算法执行所需的时间如何增加。...让我们通过比较两个经典的排序算法——冒泡排序和快速排序——来探讨时间复杂度的大小关系。
* 排序算法的分类如下: * 1.插入排序(直接插入排序、折半插入排序、希尔排序); * 2.交换排序(冒泡泡排序、快速排序); * 3.选择排序(直接选择排序、堆排序); * 4.归并排序; * 5.基数排序。 * ...
冒泡排序是一种简单的排序算法,通过重复遍历待排序序列,比较每对相邻的元素,并在必要时交换它们的位置,从而将最大的元素逐步“浮”到序列的末尾。这个过程会不断重复,直到整个序列变得有序。冒泡排序的时间...
它首先将待排序的数组元素按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个数组被分为一组,算法便终止。希尔排序的时间复杂度与增量序列...
基数排序是一种非比较型整数排序算法,它通过按数字的各个位数进行排序来实现整体序列的有序化。该算法首先确定待排序序列中最大数的位数,然后从最低位(个位)开始,依次对每一位进行排序。在排序过程中,通过创建...
归并排序的时间复杂度为O(nlogn),是一种稳定的排序算法,适用于各种规模的数据集。在Java实现中,归并排序通过递归调用mergeSortHelper方法将数组划分为更小的子数组,并在最后使用merge方法将有序子数组合并成一个...
计数排序是一种非比较型整数排序算法,特别适用于一定范围内的非负整数排序。该算法通过统计每个元素出现的次数来确定元素在排序后数组中的位置,从而达到排序的目的。计数排序的时间复杂度为O(n+k),其中n为待排序...
常见排序算法java实现,包括快速排序,归并排序,堆排序三个常用nlogn复杂度的算法
## 九种内部排序算法的Java实现及其性能测试 ### 9种内部排序算法性能比较 第九种为java.util.Arrays.sort(改进的快速排序方法) 1. 100000的随机数据集 ![](http://7xlkoc.com1.z0.glb.clouddn.com/sort1.jpg) ...
堆排序的时间复杂度为O(nlogn),是一种稳定的原地排序算法,不需要额外的存储空间。然而,堆排序在构建和调整堆的过程中需要执行多次比较和交换操作,可能相对耗时。 以下是一个用Java实现的堆排序算法示例。该示例...
本人原创,当年毕业找工作的时候整理出来的。下载后请尊重原创,不得用于谋取非法利益
三种冒泡排序算法的例子,比较区别与联系!
在Java实现中,快速排序算法通过quickSort方法接收待排序数组和左右索引作为参数,递归地调用partition方法进行数据划分,并分别对划分后的子序列进行排序。partition方法选择数组中的一个元素作为基准,通过比较和...
常用排序算法总结,包括插入排序(InsertionSort),冒泡排序(BubbleSort),选择排序(SelectionSort),快速排序(QuickSort), * 二路归并排序(MergeSort),堆排序...有每一种排序算法的复杂度分析以及实现思路~
下面的算法都打包在一个应用当中,你只需要下载安装即可,里面有算法的介绍,时间复杂度,空间复杂度,代码示例 二叉树的遍历 二叉排序树 红黑树 AVL树 图的邻接表存储构成图 有向图的创建 拓扑排序-邻接矩阵存储-...
快速排序是一种采用分治法策略的高效排序算法,其基本思想是选取一个基准元素,将数组分为两部分,使得一部分的元素都小于基准元素,另一部分的元素都大于基准元素。 快速排序过程 快速排序的过程包括选取基准、分区...