1、插入排序算法
/*
* Simple insertion sort.
* @param a an array of Comparable items.
*/
public static void insertionSort(Comparable[] a)
{
for(int p=1; p < a.length ;p++){
Comparable tmp = a[p];//临时变量
int j = p;
for(; j>0 && tmp.compareTo(a[j-1])< 0; j--)
a[j] = a[j-1];
a[j] = tmp;
}
}
时间复杂度是:O(N*N),如果输入被预先排序,运行时间将是O(N)。
算法思路:首先将需要插入排序的元素放入临时变量,然后将所有比它大的元素都向右移动一个位置,最后将临时变量复制进腾出的位置上。
2、快速排序
/*
* Quicksort algorithm(driver).
*/
public static void quicksort( Comparable[] a ){
quicksort(a,0,a.length-1);
}
/*
* Internal quicksort method that makes recursive calls.
* Uses median-of-three partitioning and a cutoff.
* 使用三者取中拆分和小数组截断点的快速排序
*/
private static void quicksort(Comparable[] a , int low, int high){
if(low + CUTOFF > high )
insertionSort(a,low,high);//测试小数组,当问题小于CUTOFF给出特定值时用插
//入排序
else{
//对low, middle, high位置处的元素进行排序,然后将它们放在合适的位置。
int middle = ( low + high )/2;
if(a[middle].compareTo(a[low]) < 0 )
swap(a, low, middle);//交换low与middle的值
if(a[high].compareTo(a[low]) < 0 )
swap(a, low, high);
if(a[high].compareTo(a[middle]) < 0 )
swap(a, middle, high);
swap(a, middle , high-1);
Comparable pivot = a[high - 1];//支点的设置
int i,j;
for(i=low, j = high-1; ;){
while( a[++i].compareTo( pivot ) < 0 )
;
while( pivot.compareTo( a[--j]) < 0 )
;
if( i >= j)
break;
swap(a, i , j);
}
swap(a, i ,high-1);//确定支点的位置
quicksort(a, low, i-1);
quicksort(a, i+1, high);
}
}
平均时间复杂度为O(N logN)
分享到:
相关推荐
用java实现了以下算法: 1、冒泡排序、冒泡排序的两种改进。 2、插入排序。 3、选择排序。 4、希尔排序。 5、归并排序。 6、快速排序。
用蛮力法实现选择排序,冒泡排序程序;用减治法实现插入排序;分治法应用-快排,合并排序,0-1背包问题;Prim算法求最小生成树。伪代码以及java代码实现
总结了常用的八大排序算法:(交换式:1、冒泡,2、快排; 选择式:3、选择, 4、堆排; 插入式:5、插入, 6、希尔; 其他:7、归并, 8、基数排序)。 并包含了Java实现的源代码。
## 九种内部排序算法的Java实现及其性能测试 ### 9种内部排序算法性能比较 第九种为java.util.Arrays.sort(改进的快速排序方法) 1. 100000的随机数据集 ![](http://7xlkoc.com1.z0.glb.clouddn.com/sort1.jpg) ...
冒泡排序、快速排序、直接插入排序、简单选择排序 等经典算法的思想介绍,大白话简单易懂。并用java实现。代码拿去即可用,不需做任何修改! 部分内容: /** * 快排:O(n*logn);如果是从小到大排序; * 思想:选...
支持任意类型数据的排序,采用5中排序算法冒泡排序,选择,插入,快速,堆排序。
java排序算法汇总 将数据结构里的排序算法使用java实现 包括:归并 快速排序 直接选择 插入。。。。
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字...
java代码实现的排序算法(冒泡,快速,简单选择,堆排,直接插入,希尔,归并),代码本身的注释不多,主要注释的还是当前排序算法的一些特点,比如时间复杂度,空间复杂度,一趟排序后数列的特点。适合了解算法性质...
用java做的一个小的排序算法演示程序,用线程控制访问,共7个算法,包括冒泡,选择,希尔,插入,归并,堆,快排。。
相关主题有:并查集算法,二分查找,栈,队列,背包,插入排序,选择排序,希尔排序,快速排序, 三切分快排,归并排序,堆排序,二分堆,二分查找树,红黑树,链表,线性哈希表,Graham扫描,kd树。 算法(二)...
用java 实现的排序系统,有冒泡、直接插入、快排、折半、选择排序5种方法实现。并且支持生成随机数或者用户自定义输入,然后选择排序算法。。挺完善的排序系统,可用eclipse直接运行,没有错误。
java实现包括插入排序、冒泡排序和快速排序算法。可以对任何简单类型和任意对象进行排序,可以支持升序、降序等多种顺序要求。用面向对象的思想,多继承实现各种排序方法,代码简单易用,附带uml图解
随机快排 O(N*logN) O(logN) 不稳定 无关 插入 直接插入排序 O(n^2) O(1) 稳定 有关 希尔排序 O(n^3/2^) O(1) 不稳定 选择 直接选择排序 O(n^2) O(1) 不稳定 无关 堆排序 O(N*logN) O(1) 不稳定 无关 分治 归并排序 ...
快排 冒泡 选择 希尔 堆 直接插入 归并一共六个算法
用Java实现的对常见7个排序算法进行演示,7个排序算法为:冒泡、插入、堆排、归并、快排、希尔、选择
讨论 了几种常见的内部排序算法及其时间复杂度: 插入排序、 起泡排序、 选择排序、 快速排 序、 希尔排序、 堆排序, 并且对这几种排序算法进行 了分析比较。着重提供 了希尔排序和堆 排序的实现程序, 以堆排序...
小白日记之八种排序算法——八种排序算法:冒泡排序、选择排序、插入排序、希尔排序、基数排序、堆排序、归并排序、快排
这是java版的算法排序合集 希望对大家有所启迪
增加了使用随机值做分割的快速排序,算法效果相比使用最后一个数做分割的快速排序较好