`
徐李99
  • 浏览: 1516 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
文章分类
社区版块
存档分类
阅读更多

最近亲测了六种排序算法:1.插入排序、2.冒泡排序、3.选择排序、4.快速排序、5.归并排序、6.希尔排序

直接上代码:

 

package xl.com;

public class Sort {	
	/**
	 * 时间复杂度:
	 * 
	 * 1.时间频度:是指 一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法
	 * 			      花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。
	 * 			      一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。 
	 * 2.时间复杂度: 在刚才提到的时间频度中,n称为问题的规模,当n不断变化时,时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此,我们引入时间
	 * 				  复杂度概念。 一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,
	 * 				 T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。 
	 */
	
	/**
	 * 空间复杂度:
	 * 
	 * 		类似于时间复杂度的讨论,一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间,
	 * 		它也是问题规模n的函数。空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间,
	 * 		包括存储算法本身所占用的存储空间,算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。
	 * 		算法的输入输出数据所占用的存储空间是由要解决的问题决定的,是通过参数表由调用函数传递而来的,它不随本算法的不同而改变。
	 * 		存储算法本身所占用的存储空间与算法书写的长短成正比,要压缩这方面的存储空间,就必须编写出较短的算法。
	 * 		算法在运行过程中临时占用的存储空间随算法的不同而异,有的算法只需要占用少量的临时工作单元,而且不随问题规模的大小而改变,
	 * 		我们称这种算法是“就地/"进行的,是节省存储的算法,如这一节介绍过的几个算法都是如此;有的算法需要占用的临时工作单元数与解决问题的规模n有关,
	 * 		它随着n的增大而增大,当n较大时,将占用较多的存储单元,例如将在第九章介绍的快速排序和归并排序算法就属于这种情况。
	 */
	
	/**
	 * 插入排序
	 * 基本思想:每次将无序区中第一个元素与有序区中的元素进行比较,放入恰当的位置
	 * 时间复杂度:O(n2)
	 * 稳定性:稳定
	 * @param data
	 * @return
	 */
	public void insertSort(int[] data){
		for(int index=1;index<data.length;index++){
			int currPosition;
			currPosition=index;
			int key=data[index];
			while(currPosition>0&&data[currPosition-1]>key){
				data[currPosition]=data[currPosition-1];
				currPosition--;
			}
			data[currPosition]=key;
		}
	}
	
	/**
	 * 冒泡排序
	 * 基本思想:每次比较相邻两个元素大小,将大的往后移,每次能都将最大的元素放到最后面
	 * 时间复杂度:O(n2)
	 * 稳定性:稳定
	 * @param data
	 */
	public void bubbleSort(int[] data){
		for(int i=data.length-1;i>1;i--){
			for(int j=0;j<i;j++){
				if(data[j]>data[j+1]){
					int temp=data[j];
					data[j]=data[j+1];
					data[j+1]=temp;
				}
			}
		}
	}
	
	/**
	 * 选择排序
	 * 基本思想:每次选择未排序序列中的最小元素放在已排序序列后面。关键是找到最小元素即可
	 * 时间复杂度:O(n2)
	 * 稳定性:稳定
	 * @param data
	 */
	public void selectSort(int[] data){
		for(int i=0;i<data.length-1;i++){
			int min=i;
			for(int j=i;j<data.length-1;j++){//在data[j,data.length-1]中将data[j]看做是最小值
				if(data[j]<data[min]){
					min=j;
				}
			}
			if(min!=i){
				int temp=data[i];
				data[i]=data[min];
				data[min]=temp;
			}
		}
	}
	
	/**
	 * 快速排序
	 * 基本排序:每次排序将选择的基准元素放在准确位置,使得左边是小于它的元素,右边是大于它的元素。再进行递归
	 * 时间复杂度:O(nlogn)
	 * 稳定性:不稳定
	 * @param data
	 * @param start
	 * @param end
	 */
	public void quickSort(int[] data,int low,int high){		
        if(low<high){ 
            int middle = getMiddle(data,low,high);
            quickSort(data, 0, middle-1);
            quickSort(data, middle+1, high);
        }
	}

	private static int getMiddle(int[] data, int low, int high) {
        int temp = data[low];//基准元素
        while(low<high){
            //找到比基准元素小的元素位置
            while(low<high && data[high]>=temp){
                high--;
            }
            data[low] = data[high]; 
            while(low<high && data[low]<=temp){
                low++;
            }
            data[high] = data[low];
        }
        data[low] = temp;
        return low;
	}
	
	/**
	 * 归并排序
	 * 基本思想:将要排序的序列一分为二,二分为四进行递归,最后再合并。
	 * 时间复杂度:O(nlogn) 
     * 稳定性:稳定 
	 * @param data
	 * @param left
	 * @param right
	 */
	public void mergeSort(int[] data,int low,int high){
		int mid=(high+low)/2;
		if(low<high){
			mergeSort(data,low,mid);
			mergeSort(data,mid+1,high);
			merge(data,low,mid,high);
		}
	}
	public void merge(int[] data,int low,int mid,int high){//归并
		int[] temp=new int[high-low+1];               //用于中转的新的数组
		int i=low;//左指针
		int j=mid+1;//中指针
		int k=0;
		while(i<=mid&&j<=high){
			if(data[i]<=data[j]){                   //用于把小的数放入新的数组
				temp[k++]=data[i++];
			}else{
				temp[k++]=data[j++];
			}                                  //k用作新数组的小标标记
		}
		while(i<=mid){                                 //表示左边的数组元素全部移到了新数组中
			temp[k++]=data[i++];
		}
		while(j<=high){                                  //表示右边的数组元素全部移到了新数组中
			temp[k++]=data[j++];
		}
		for(int s=0;s<temp.length;s++){                      //再将新数组复制到原数组中
			data[s+low]=temp[s];
		}
	}
	
	/**
	 * 希尔排序
	 * 基本思想:是在普通插入排序的基础上进行改进。将要排序的序列分为gap组,对每组的元素进行插入排序.再减小gap的值直到为1
	 * 时间复杂度:与增量gap有关,下界是O(nlogn)
	 * 稳定性:不稳定
	 * @param data
	 */
	public void shellSort(int[] data){
		int size = data.length;  
	    for(int gap = size/2; gap>=1; gap /= 2) {  
	        for(int i=gap; i<size; i++) {  
	            int k;  
	            int temp = data[i];  
	            for(k = i-gap; k>=0 && data[k] > temp; k -= gap) {  
	                data[k+gap] = data[k];  
	            }  
	            data[k+gap] = temp;  
	        }  
	    }  
	}  
	/*************************************************************************************/
	/**
	 * 用来显示数组
	 * @param data
	 */
	public void showAfter(int[] data){
		String result="";
		for(int index=0;index<data.length;index++){
			result+=data[index];
			result+=",";
		}
		System.out.println("排序后:"+result);
	}
	public void showBefore(int[] data){
		String result="";
		for(int index=0;index<data.length;index++){
			result+=data[index];
			result+=",";
		}
		System.out.println("排序前:"+result);
	}
	/**
	 * 测试
	 * @param args
	 */
	public static void main(String[] args){
		Sort sort=new Sort();
		int[] dbl={8,1,2,5,4,3,9,6,4,4,4,8,9,99,77,55,66,3,5,12,12};
		sort.showBefore(dbl);
//		sort.insertSort(dbl);
//		sort.bubbleSort(dbl);
//		sort.selectSort(dbl);
//		sort.quickSort(dbl, 0, dbl.length-1);
//		sort.mergeSort(dbl, 0, dbl.length-1);
		sort.shellSort(dbl);
		sort.showAfter(dbl);
		
	}
}

 

分享到:
评论

相关推荐

    常用各种排序算法Java的实现_差不多了__.rar

    本资源"常用各种排序算法Java的实现_差不多了__.rar"显然是一个包含了各种经典排序算法Java实现的压缩文件,对于学习和理解这些算法的开发者来说极具价值。 首先,我们来概述一下常见的排序算法: 1. 冒泡排序:是...

    各种排序算法比较(java实现)

    `Algorithm.java`文件可能包含了这些排序算法的Java实现代码,而`常见排序算法的实现与性能比较.doc`文档则可能详细比较了这些算法的性能和适用场景。`readme.txt`文件可能是对整个项目的简要说明,包括如何运行和...

    各种排序算法java实现

    在提供的文件中,我们可以看到有四种经典的排序算法的Java实现:插入排序、冒泡排序、选择排序以及希尔排序。 **插入排序**: 插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据...

    基数排序算法 java实现

    基数排序是一种非比较型整数排序算法,它的原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。这种算法对于大数据量的排序尤其有效,因为其时间复杂度为线性,即O(n*k),其中n是待排序的元素数量,k是每...

    常见的七大排序算法Java实现.zip

    本压缩包"常见的七大排序算法Java实现.zip"包含了七种经典的排序算法在Java语言中的实现。尽管文件列表中并未明确列出每种排序算法的名称,但根据常规,这七大排序算法可能包括冒泡排序、插入排序、选择排序、快速...

    基于java语言十大经典排序算法

    **基于Java语言十大经典排序算法** 排序算法是计算机科学中不可或缺的一部分,...通过阅读《基于java语言十大排序算法.docx》文档,你可以深入学习这些排序算法的实现细节,结合图形解释,有助于更好地理解和记忆。

    常用排序算法java演示

    本文将深入探讨标题"常用排序算法java演示"中涉及的知识点,包括排序算法的原理、Java实现方式以及其在实际应用中的图形演示。 首先,让我们逐一了解几种常见的排序算法: 1. **冒泡排序(Bubble Sort)**:这是一...

    排序算法JAVA实现,eclipse+txt

    在IT领域,排序算法是计算机科学中的核心概念,特别是在数据结构和算法分析中。Java作为一种广泛应用的编程语言,提供了丰富的...这个资料包中的Java实现和Eclipse工程,可以帮助开发者深入理解和实践这些排序算法。

    Java排序算法实现

    Java排序算法实现 Java排序算法实现 Java排序算法实现

    IT面试笔试-各种排序算法Java实现

    【IT面试笔试中的排序算法Java实现】 在IT面试和笔试中,掌握各种排序算法的实现是必不可少的技能。本文将详细介绍几种经典的排序算法,并提供Java语言的实现代码,包括冒泡排序、插入排序、选择排序和快速排序。...

    几种经典的排序算法java实现

    冒泡排序、快速排序、直接插入排序、简单选择排序 等经典算法的思想介绍,大白话简单易懂。并用java实现。代码拿去即可用,不需做任何修改! 部分内容: /** * 快排:O(n*logn);如果是从小到大排序; * 思想:选...

    三种线性排序算法Java实现

    本资源提供的Java实现包括了三种线性排序算法:桶排序(Bucket Sort)、基数排序(Radix Sort)和计数排序(Counting Sort)。这三种算法在特定条件下可以达到线性的平均或最好时间复杂度,效率相对较高。 1. **桶...

    内部排序算法java实现

    这里我们将深入探讨Java实现的几种内部排序算法,包括希尔排序、快速排序、堆排序、归并排序、冒泡排序、插入排序和选择排序。 首先,希尔排序是一种基于插入排序的算法,通过将原始数组分解成多个子序列来提高效率...

    各类排序算法java的实现.CHM

    各类排序算法java的实现.CHM 各类排序算法java的实现.CHM

    JAVA写的6种内部排序算法简单实现

    在编程领域,排序算法是数据结构与算法中的基础部分,对于任何程序员来说,理解和掌握排序算法都是非常重要的。这里我们主要探讨的是使用Java语言实现的六种内部排序算法。内部排序是指在内存中完成的排序过程,它不...

    三种排序算法java实现

    这里我们主要关注三种排序算法的Java实现:快速排序、桶排序以及插入排序。这三种算法各有特点,适用于不同的场景。 首先,快速排序(QuickSort)是由C.A.R. Hoare在1960年提出的,它是一种分治策略的典型应用。...

Global site tag (gtag.js) - Google Analytics