`
uule
  • 浏览: 6351833 次
  • 性别: Icon_minigender_1
  • 来自: 一片神奇的土地
社区版块
存档分类
最新评论

JAVA排序汇总

阅读更多

JAVA排序算法

排序算法复习(Java实现)(一): 插入,冒泡,选择,Shell,快速排序

排序算法复习(Java实现)(二): 归并排序,堆排序,桶式排序,基数排序

关于快速排序和归并排序的时间复杂度

 

 常见排序算法及对应的时间复杂度和空间复杂度

 

排序算法的分类如下:
  1.插入排序(直接插入排序、折半插入排序、希尔排序);
  2.交换排序(冒泡排序、快速排序);
  3.选择排序(直接选择排序、堆排序);
  4.归并排序;
  5.基数排序。

 

交-冒快

选-直堆

插-直希

归并


  关于排序方法的选择:

  (1)若n较小(如n≤50),可采用直接插入或直接选择排序。
   当记录规模较小时,直接插入排序较好;否则因为直接选择移动的记录数少于直接插人,应选直接选择排序为宜。
  (2)若文件初始状态基本有序(指正序),则应选用直接插人、冒泡或随机的快速排序为宜;
  (3)若n较大,则应采用时间复杂度为O(nlgn)的排序方法:快速排序、堆排序或归并排序。

入口:

	public static void main(String[] args) {
		int[] a = {4,2,13,10,8};
		printArray(a);
		//sort.reverse(a);
		//selectSort(a);
		//insertSort(a);
		   //shellSort(a);
		quickSort(a);
	}

  公共部分:

	public static void printArray(int[] a){
		for(int m : a){
			System.out.print(m+" ");
		}		
	}
	/**	
	 * 反转数组的方法
	 * @param data
	 */
	public static void reverse(int[] data) {
		int length = data.length;
		int temp = 0;// 临时变量
		for (int i = 0; i < length / 2; i++) {
			temp = data[i];
			data[i] = data[length - 1 - i];
			data[length - 1 - i] = temp;
		}
		printArray(data);// 输出到转后数组的值
	}

 

1、冒泡排序:

这可能是最简单的排序算法了,算法思想是每次从数组末端开始比较相邻两元素,把第i小的冒泡到数组的第i个位置。i从0一直到N-1从而完成排序。(当然也可以从数组开始端开始比较相邻两元素,把第i大的冒泡到数组的第N-i个位置。i从0一直到N-1从而完成排序。)

 

    两两相比较,最小的数到最上面
    data.length个数需比较data.length-1次

 

从头开始,把最大的冒到最后面

从尾开始,把最小的冒到最前面

 

冒头大尾小

public void bubbleSort(int[] data) {

                      //比较的轮数
                    for (int i = 1; i < data.length; i++) {
                            //将相邻两个数进行比较,较大的数往后冒泡
                            for (int j = 0; j < data.length - i; j++) {
                                   if (data[j] > data[j + 1]) {
                                          //交换相邻两个数
                                          swap(data, j, j + 1);
                                   }
                            }
                     }
            printArray(data);//输出冒泡排序后的数组值
       }

 

2.插入排序:

该算法在数据规模小的时候十分高效

 

	/**
	  * 插入排序 ---与前面数比较
	  * 该算法在数据规模小的时候十分高效
	  * 
	  * 从第二个数开始,每个数都与其前面的所有数比较,每次大循环后该数前面的所有数都已排好续
	  * 如第二个数与第一个数比较,小循环一次
	  * 第3个数与前两个数比较,小循环两次
	  */
	public static void insertSort(int[] a) {
		int temp;
		for (int i = 1; i < a.length; i++) {
			for (int j = i; j > 0; j--) {
				if (a[j] < a[j - 1]) {
					temp = a[j];
					a[j] = a[j - 1];
					a[j - 1] = temp;
				}
			}
		}
		System.out.print("\n插入排序结果:");
		printArray(a);
	}

 

3.选择排序:

选择排序相对于冒泡来说,它不是每次发现逆序都交换,而是在找到全局第 i 小的时候记下该元素位置,最后跟第i个元素交换,从而保证数组最终的有序

 

相对与插入排序来说,选择排序每次选出的都是全局第i小的,不会调整前i个元素了。

 

	/**
	 * 选择排序---使用索引
	 * 每个元素都与它后面的所有元素比较,当后面元素小于当前索引值时,把该元素的位置赋给索引,
	 * 使其成为新的索引,然后	再继续比较
	 * 
	 * 即设置一个索引值,后面每个元素都与索引比较,当其比索引值小时,替换索引序号
	 * 这样最后索引代表的值是每次循环中数组的最小值
	 */
	public static void selectSort(int[] a) {
		int temp;
		for (int i = 0; i < a.length; i++) {
			int lastIndex = i;
			for (int j = i + 1; j < a.length; j++) {
				if (a[j] < a[lastIndex]) {
					lastIndex = j;
				}
			}
			temp = a[i];
			a[i] = a[lastIndex];
			a[lastIndex] = temp;
		}
		System.out.print("\n选择排序结果:");
		printArray(a);
	}

 

4、快速排序

快速排序是目前使用可能最广泛的排序算法了。

一般分如下步骤:

1)选择一个枢纽元素(可以是第一个,也可以是中间的那个)

2)使用该枢纽元素分割数组使得比该元素小的元素在它的左边,比它大的在右边。并把枢纽元素放在合适的位置。

3)根据枢纽元素最后确定的位置,把数组分成三部分,左边的,右边的,枢纽元素自己,对左边的,右边的分别递归调用快速排序算法即可。

快速排序的核心在于分割算法,也可以说是最有技巧的部分。

 

int a[101],n;//定义全局变量,这两个变量需要在子函数中使用 
void quicksort(int left,int right) 
{ 
    int i,j,t,temp; 
    if(left>right) 
       return; 
                                
    temp=a[left]; //temp中存的就是基准数 
    i=left; 
    j=right; 
    while(i!=j) 
    { 
                   //顺序很重要,要先从右边开始找 
                   while(a[j]>=temp && i<j) 
                            j--; 
                   //再找右边的 
                   while(a[i]<=temp && i<j) 
                            i++; 
                   //交换两个数在数组中的位置 
                   if(i<j) 
                   { 
                            t=a[i]; 
                            a[i]=a[j]; 
                            a[j]=t; 
                   } 
    } 
    //最终将基准数归位 
    a[left]=a[i]; 
    a[i]=temp; 
                             
    quicksort(left,i-1);//继续处理左边的,这里是一个递归的过程 
    quicksort(i+1,right);//继续处理右边的 ,这里是一个递归的过程 
} 
int main() 
{ 
    int i,j,t; 
    //读入数据 
    scanf("%d",&n); 
    for(i=1;i<=n;i++) 
                   scanf("%d",&a[i]); 
    quicksort(1,n); //快速排序调用 
                             
    //输出排序后的结果 
    for(i=1;i<=n;i++) 
        printf("%d ",a[i]); 
    getchar();getchar(); 
    return 0; 
} 

 

 

坐在马桶上看算法:快速排序

java实现快速排序

 

 

5、

  • 大小: 43.1 KB
分享到:
评论

相关推荐

    JAVA排序汇总 java应用中一些比较经典的排序算法

    【JAVA排序汇总】Java编程语言中,排序是数据处理中非常基础且重要的操作。本文将对几种经典的排序算法进行简要介绍和分析。 1. **插入排序**: 插入排序分为直接插入排序和折半插入排序。直接插入排序是将每个...

    JAVA 排序汇总 数据结构所有排序算法 的java实现

    ### JAVA排序汇总知识点详解 #### 一、概述 在计算机科学中,排序是一种常见的操作,用于将一组数据按照一定的规则进行排列。Java作为一种广泛应用的编程语言,在数据结构学习与实际项目开发中扮演着重要角色。本...

    JAVA排序汇总 各种排序

    在Java编程语言中,排序是数据处理中非常基础且重要的操作。本文将全面解析Java中的各种排序算法,帮助你理解并掌握它们的核心概念、实现方式以及适用场景。 1. 冒泡排序(Bubble Sort) 冒泡排序是最简单的排序...

    JAVA排序汇总.txt

    ### JAVA排序汇总 #### 排序算法的分类与选择指南 在计算机科学中,排序算法是一种重要的数据处理技术,用于将一系列数据按照特定规则进行排列。根据不同的特性,排序算法可以分为以下几类: 1. **插入排序**:...

    java 排序汇总 排序 算法

    ### Java排序算法详解 在Java编程语言中,排序算法是数据结构与算法领域的重要组成部分,广泛应用于各种场景中。本文将详细介绍几种常见的排序算法,并通过示例代码进行讲解。 #### 1. 冒泡排序(Bubble Sort) ...

    JAVA经典排序汇总

    【正文】 ...总的来说,本文涵盖了Java中主要的排序算法,通过实例代码和性能分析,有助于读者系统地学习和掌握排序算法。无论是初学者还是经验丰富的开发者,都能从中受益,提升自己的编程能力。

    Java排序算法汇总

    本文将深入探讨标题"Java排序算法汇总"所涵盖的八大排序算法:起泡排序、堆排序、插入排序、归并排序、快速排序、选择排序、Shell排序以及优化后的归并排序和快速排序。 1. 起泡排序(Bubble Sort): 起泡排序是一...

    Java排序算法汇总大全.doc

    Java排序算法汇总大全 在计算机科学中,排序算法是用于对数据序列进行排列的算法,以便根据特定标准对其进行组织。本文将详细介绍Java中常见的几种排序算法,并提供它们的基本原理、性能分析以及适用场景。 1. ...

    排序排序 array to object?? attachment

    在文件列表中,“JAVA排序汇总.doc”是一个文档文件,很可能包含了对Java中各种排序算法的详细解释、示例代码以及可能的性能分析。Java作为面向对象的语言,其内置的`Collections.sort()`和`Arrays.sort()`方法提供...

    JAVA内部排序算法汇总

    ### JAVA内部排序算法汇总 #### 一、概述 在计算机科学中,排序是一种常见的操作,用于将一组数据按照特定顺序排列。本篇文章基于一个具体的Java实现案例,详细介绍了几种常用的内部排序算法,包括直接插入排序、...

    java多线程排序

    java多线程排序源程序,三种排序算法。希尔排序,快速排序,堆排序。

    java常用的7大排序算法汇总

    ### Java常用的七大排序算法 #### 1. 插入排序算法 插入排序是一种简单直观的排序算法。它的基本思想是:对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。 - **算法步骤**: 1. 将第一待排序...

    排序汇总(Java).pdf

    总结来说,这个文档提供了对Java排序算法的概述和一个简单的冒泡排序实现,帮助读者理解排序算法的基本原理,并提供了实践代码作为参考。对于学习和理解排序算法,尤其是Java编程中的排序,这是一个很好的起点。

Global site tag (gtag.js) - Google Analytics