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、