java几种排序算法的实现及简单分析

本文实例讲述了java几种排序算法的实现及简单分析。分享给大家供大家参考。具体如下：

package test;
public class first {
/*普通的插入排序*/
public void insertSort(int[] list) {
int i, j;
list[0] = -999;
//相当于设置一个监视哨兵，不用判断是否越界，
//但要求数组从第二个数开始即i=1开始存储
for (i = 1; i < list.length; i++) {
j = i;
while (list[j] < list[j - 1]) {
int temp = list[j];
list[j] = list[j - 1];
list[j - 1] = temp;
j = j - 1;
}
}
}
/*折半插入，在直接插入的基础上，添加二叉查找*/
public void binInsertSort(int[] r, int low, int high) {
for (int i = low + 1; i <= high; i++)
{
int temp = r[i]; // 保存待插入元素
int hi = i - 1;
int lo = low; // 设置初始区间
while (lo <= hi)
{ // 折半确定插入位置
int mid = (lo + hi) / 2;
if (temp < r[mid])
hi = mid - 1;
else
lo = mid + 1;
}
for (int j = i - 1; j > hi; j--)
r[j + 1] = r[j]; // 移动元素
r[hi + 1] = temp; // 插入元素
}
}
/*希尔排序或shell */
public void shellSort(int[] r, int low, int high, int[] delta){
for (int k=0;k<delta.length;k++)
shellInsert(r, low, high, delta[k]);
}
private void shellInsert(int[] r, int low, int high, int deltaK){
for (int i=low+deltaK; i<=high; i++)
if (r[i]<r[i-deltaK]){
int temp = r[i];
int j = i-deltaK;
for(; j>=low&&temp<r[j]; j=j-deltaK)
r[j+deltaK] = r[j];
r[j+deltaK] = temp;
}
}
/*简单的选择交换*/
public void selectSort(int[] r, int low, int high) {
for (int k = low; k < high - 1; k++) { // 作n-1 趟选取
int min = k;
for (int i = min + 1; i <= high; i++)
// 选择关键字最小的元素
if (r[i] < r[min])
min = i;
if (k != min) {
int temp = r[k]; // 关键字最小的元素与元素r[k]交换
r[k] = r[min];
r[min] = temp;
}// end of if
}
}
/*堆排序-大顶堆*/
public void heapSort(int[] r){
int n = r.length - 1;
for (int i=n/2; i>=1; i--)
heapAdjust(r,i,n);
for (int i=n; i>1; i--){
int temp = r[1];
r[1] = r[i];
r[i] = temp;
heapAdjust(r,1,i-1);
}
}
//调整堆
private void heapAdjust(int[] r, int low, int high){
int temp = r[low];
for (int j = 2 * low; j <= high; j = j * 2) {
if (j < high && r[j] < r[j + 1])
j++;
if (temp > r[j])
break;
r[low] = r[j];
low = j;
}
r[low] = temp;
}
public static void main(String[] args) {
first fs = new first();
int[] a = { 100, 9, 8, 9, 9, 7, 7, 0, 0, 99, 55, 7, 6, 5, 4, 3, 2, 1 };
int[] k={5,3,1};
// fs.insertSort(a);
//fs.binInsertSort(a, 0, a.length - 1);
//fs.shellSort(a, 0,a.length-1,k);
//fs.selectSort(a, 0, a.length-1);
fs.heapSort(a);
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
}
}
}

插入排序、交换排序、选择排序、归并排序等排序方法，都有一个共同的特点，那就是它们都是通过比较元素的大小来确定元素之间的相对位置的，即上述排序方法都是基于比较的排序方法。下面，我们就基于比较的排序方法进行一个对比和总结。
我们主要从算法的平均时间复杂度、最坏时间复杂度、空间复杂度以及排序的稳定性等方面，对各中排序方法加以比较。

排序方法 平均时间复杂度最坏时间复杂度空间复杂度 稳定性
直接插入排序 Ο(n2) Ο(n2) Ο(1) 稳定
起泡排序 Ο(n2) Ο(n2) Ο(1) 稳定
快速排序 Ο(n log n) Ο(n2) Ο(log n) 不稳定
简单选择排序 Ο(n2) Ο(n2) Ο(1) 不稳定
堆排序 Ο(n log n) Ο(n log n) Ο(1) 不稳定
归并排序 Ο(n log n) Ο(n log n) Ο(n) 稳定

从时间性能上看，快速排序是所有排序算法中实际性能最好的，然而快速排序在最坏情况下的时间性能不如堆排序和归并排序。这一点可以通过对快速排序进行改进来避免，一种通过随机选择枢轴元素的随机快速排序，可以使得出现最坏情况出现的几率非常小，在实际的运用中可以认为不存在。在堆排序和归并排序的比较中，当n 较大时，归并排序所需时间较少，然而它需要较多的辅助存储空间。

从方法稳定性上来看，大多数时间复杂度为Ο(n2)的排序均是稳定的排序方法，除简单选择排序之外。而多数时间性能较好的排序方法，例如快速排序、堆排序、希尔排序都是不稳定的。一般来说，排序过程中的比较是在相邻的两个元素之间进行的排序方法是稳定的。

并且，排序方法的稳定性是由方法本身决定的，对于不稳定的排序方法而言，不管其描述形式如何，总能找到一种不稳定的实例。

综上所述，上面讨论的所有排序方法中，没有哪一个是绝对最优的，在实际的使用过程中，应当根据不同情况选择适当的排序方法。

希望本文所述对大家的java程序设计有所帮助。

赞 (0)

相关推荐

  • Java数据结构及算法实例：冒泡排序 Bubble Sort

    /** * 冒泡排序估计是每本算法书籍都会提到的排序方法. * 它的基本思路是对长度为N的序列,用N趟来将其排成有序序列. * 第1趟将最大的元素排在序列尾部,第2趟将第2大的元素排在倒数第二的位置, * 即每次把未排好的最大元素冒泡到序列最后端. * 该排序方法实际上分为两重循环,外层循环:待排元素从数组的第1个元素开始. * 内层循环:待排元素从数组的第1个元素开始,直到数组尾端未排过的元素. * 在内循环中,如果遇到前面元素比其后的元素大就交换这两个元素的位置. * 由此可见冒泡排序的复杂

  • Java数据结构及算法实例：插入排序 Insertion Sort

    /** * 选择排序的思想: * 每次循环前,数组左边都是部分有序的序列, * 然后选择右边待排元素,将其值保存下来 * 依次和左边已经排好的元素比较 * 如果小于左边的元素,就将左边的元素右移一位 * 直到和最左边的比较完成,或者待排元素不比左边元素小 */ package al; public class InsertionSort { public static void main(String[] args) { InsertionSort insertSort = new Insert

  • Java排序算法总结之希尔排序

    本文实例讲述了Java排序算法总结之希尔排序.分享给大家供大家参考.具体分析如下: 前言:希尔排序(Shell Sort)是插入排序的一种.是针对直接插入排序算法的改进.该方法又称缩小增量排序,因DL．Shell于1959年提出而得名.本文主要介绍希尔排序用Java是怎样实现的. 希尔排序(缩小增量法) 属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序.希尔排序并不稳定,O(1)的额外空间,时间复杂度为O(N*(logN)^2).最坏的情况下的执行效率和在平均情况下的执行效率相

  • java实现快速排序的方法

    本文实例讲述了java实现快速排序的方法.分享给大家供大家参考.具体实现方法如下: public class Quick { public static int[] Data = { 9, 8, 7, 4, 1, 12, 15, 63, 15, 20 }; public static void quick(int left, int right) { int i, j; int Pivot; int temp; i = left; j = right; Pivot = Data[(left+ri

  • JAVA四种基本排序方法实例总结

    本文实例讲述了JAVA四种基本排序方法.分享给大家供大家参考.具体如下: JAVA四种基本排序,包括冒泡法,插入法,选择法,SHELL排序法.其中选择法是冒泡法的改进,SHELL排序法是 插入法的改进.所以从根本上来说可以归纳为两种不同的排序方法:即:插入法&冒泡法 一 插入法: 遍历排序集合,每到一个元素时,都要将这个元素与所有它之前的元素遍历比较一遍,让符合排序顺序的元素挨个移动到当前范围内它最应该出现的位置.交换是相邻遍历移动,双重循环控制实现.这种排序法属于地头蛇类型,在我的地牌上我要把

  • Java数据结构及算法实例：选择排序 Selection Sort

    /** * 选择排序的思想: * 每次从待排序列中找到最小的元素, * 然后将其放到待排的序列的最左边,直到所有元素有序 * * 选择排序改进了冒泡排序,将交换次数从O(N^2)减少到O(N) * 不过比较次数还是O(N) */ package al; public class SelectSort { public static void main(String[] args) { SelectSort selectSort = new SelectSort(); int[] elements

  • java中List对象排序通用方法

    本文实例讲述了java中List对象排序通用方法.分享给大家供大家参考.具体分析如下: 在数据库中查出来的列表list中,往往需要对不同的字段重新排序,一般的做法都是使用排序的字段,重新到数据库中查询.如果不到数据库查询,直接在第一次查出来的list中排序,无疑会提高系统的性能. 只要把第一次查出来的结果存放在session中,就可以对list重新排序了.一般对list排序可以使用Collections.sort(list),但如果list中包含是一个对象的话,这种方法还是行不通的.那要怎么排序

  • java几种排序算法的实现及简单分析

    本文实例讲述了java几种排序算法的实现及简单分析.分享给大家供大家参考.具体如下: package test; public class first { /*普通的插入排序*/ public void insertSort(int[] list) { int i, j; list[0] = -999; //相当于设置一个监视哨兵,不用判断是否越界, //但要求数组从第二个数开始即i=1开始存储 for (i = 1; i < list.length; i++) { j = i; while (

  • 7种排序算法的实现示例

    复制代码 代码如下: #include <stdio.h>#include <stdlib.h>#include <time.h> void BubbleSort1 (int n, int *array) /*little > big*/{ int i, j; for (i=0; i<n-1; i++) {  for (j=n-1; j>i; j--)  {   if (array[j] < array[j-1])   {    int temp

  • Java十大经典排序算法的实现图解

    Java十大经典排序算法的实现图解

    目录 前言 一.排序算法 1.排序算法概述(百度百科) 2.<数据结构与算法>中的排序算法 3.算法分析 二.十大经典排序算法(Java开发版) 1.冒泡排序 2.快速排序 3.基数排序 4.插入排序 5.选择排序 6.希尔排序 7.归并排序 8.计数排序 9.堆排序 10.桶排序 前言 本文章主要是讲解我个人在学习Java开发环境的排序算法时做的一些准备,以及个人的心得体会,汇集成本篇文章,作为自己对排序算法理解的总结与笔记. 内容主要是关于十大经典排序算法的简介.原理.动静态图解和源码实现

  • 详解Python排序算法的实现(冒泡,选择,插入,快速)

    详解Python排序算法的实现(冒泡,选择,插入,快速)

    目录 1. 前言 2. 冒泡排序算法 2.1 摆擂台法 2.2 相邻两个数字相比较 3. 选择排序算法 4. 插入排序 5. 快速排序 6. 总结 1. 前言 所谓排序,就是把一个数据群体按个体数据的特征按从大到小或从小到大的顺序存放. 排序在应用开发中很常见,如对商品按价格.人气.购买数量……显示. 初学编程者,刚开始接触的第一个稍微有点难理解的算法应该是排序算法中的冒泡算法. 我初学时,“脑思维”差点绕在 2 个循环结构的世界里出不来了.当时,老师要求我们死记冒泡的口诀,虽然有点搞笑,但是当

  • php计数排序算法的实现代码(附四个实例代码)

    计数排序只适合使用在键的变化不大于元素总数的情况下.它通常用作另一种排序算法(基数排序)的子程序,这样可以有效地处理更大的键. 总之,计数排序是一种稳定的线性时间排序算法.计数排序使用一个额外的数组C ,其中第i个元素是待排序数组 A中值等于 i的元素的个数.然后根据数组C 来将A中的元素排到正确的位置. 通常计数排序算法的实现步骤思路是: 1.找出待排序的数组中最大和最小的元素: 2.统计数组中每个值为i的元素出现的次数,存入数组C的第i项: 3.对所有的计数累加(从C中的第一个元素开始,每一

  • C++深入浅出讲解希尔排序算法的实现

    C++深入浅出讲解希尔排序算法的实现

    目录 希尔排序 1.基本思想 预排序 2.算法实现 3.时间复杂度 插入排序分为两种:直接插入排序&希尔排序 希尔排序 1.基本思想 希尔排序是在直接插入排序基础上的优化,属于非常牛掰的一个排序. 核心思想: 先进行预排序,让数组接近有序: 直接插入排序 预排序 预排序步骤: 分组排,假设gap==3,间隔为gap的为一组,然后分别使用插入排序的思想对这gap组数据进行排序 多组间隔为gap的预排序,gap由大变小,gap越大,大的数可以越快的到后面,小的数可以越快得到前面,gap越大,预排完越

  • Java数据结构之KMP算法的实现

    目录 问题介绍 暴力求解 知识补充 Next示例 Next代码 匹配示例 匹配代码 完整代码 本次我们介绍数据结构中的KMP算法,我们会从下面几个角度来介绍: 问题介绍 首先我们先介绍适用于KMP算法的问题: 给定一个字符串S,以及一个模式串P,所有字符串中只包含大小写英文字母以及阿拉伯数字. 模式串P在字符串S中多次作为子串出现. 求出模式串P在字符串S中所有出现的位置的起始下标. 我们给出一个问题的简单示例: // 输入 p长度 p s长度 s 3 aba 5 ababa // 输出结果 0

  • python常用排序算法的实现代码

    这篇文章主要介绍了python常用排序算法的实现代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 排序是计算机语言需要实现的基本算法之一,有序的数据结构会带来效率上的极大提升. 1.插入排序 插入排序默认当前被插入的序列是有序的,新元素插入到应该插入的位置,使得新序列仍然有序. def insertion_sort(old_list): n=len(old_list) k=0 for i in range(1,n): temp=old_lis

  • C/C++浅析邻接表拓扑排序算法的实现

    C/C++浅析邻接表拓扑排序算法的实现

    目录 前言 一.拓扑排序算法的思路 二.实现步骤 1.求个顶点的入度 2.拓扑排序的实现 三.测试结果 总结 前言 在软件开发.施工过程.教学安排等等的一系列活动中,往往需要一个有向无环图来表示其是否成成功进行下去. 在一个有向图为顶点表示活动的网中,我们称为AOV网(Activity On Vertex Network).设G={V,E}是一个具有n个顶点的有向图,V中的顶点序列v1,v2,…,vn,满足若从顶点vi到vj有一条路径,则在顶点序列中顶点vi必在vj之前.则我们称这样的顶点为一个

  • PHP四种排序算法实现及效率分析【冒泡排序,插入排序,选择排序和快速排序】

    本文实例讲述了PHP四种排序算法实现及效率分析.分享给大家供大家参考,具体如下: PHP的四种基本排序算法为:冒泡排序.插入排序.选择排序和快速排序. 下面是我整理出来的算法代码: 1. 冒泡排序: 思路:对数组进行多轮冒泡,每一轮对数组中的元素两两比较,调整位置,冒出一个最大的数来. //简单版: function bubbleSort($arr) { $n = count($arr); for($i=1;$i<$n;$i++) { //冒泡的轮数(最多$n-1轮) for($j=0;$j<

随机推荐