java数组排序示例(冒泡排序、快速排序、希尔排序、选择排序)

时间:2022-03-08 10:18:20

快速排序法主要是运用了Arrays中的一个方法Arrays.sort()实现。

冒泡法是运用遍历数组进行比较,通过不断的比较将最小值或者最大值一个一个的遍历出来。

选择排序法是将数组的第一个数据作为最大或者最小的值,然后通过比较循环,输出有序的数组。

插入排序是选择一个数组中的数据,通过不断的插入比较最后进行排序。
 

复制代码代码如下:


package com.firewolf.sort;

 

public class MySort {

 /**
  * @param args
  */
 public static void main(String[] args) {
  int array[] = {45,32,54,12,43,65,11,3,43,6,33,90,44,1,178};
  MySort mySort = new MySort();
  mySort.insertSort(array);
  System.out.print("插入排序结果 :  ");
  mySort.printArray(array);
  System.out.println();
  mySort.bubbleSort(array);
  System.out.print("冒泡排序结果 :  ");
  mySort.printArray(array);
  mySort.qsort(array);
  System.out.println();
  System.out.print("快速排序结果 :  ");
  mySort.printArray(array);
  mySort.shellSort(array);
  System.out.println();
  System.out.print("希尔排序结果 :  ");
  mySort.printArray(array);
  mySort.selectSort(array);
  System.out.println();
  System.out.print("选择排序结果 :  ");
  mySort.printArray(array);
 }

 /**
  * 直接插入排序
  * 基本思想:在要排序的一组数中,假设前面(n-1)[n>=2] 个数已经是排好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数也是排好顺序的。如此反复循环,直到全部排好顺序
  */
 public void insertSort(int[] array){
  int temp=0;  
     for(int i=1;i<array.length;i++){  
        int j=i-1;  
        temp=array[i];  
        for(;j>=0&&temp<array[j];j--){  
         array[j+1]=array[j];                       //将大于temp的值整体后移一个单位  
        }  
        array[j+1]=temp;  
     } 
 }

 /**
  * 冒泡排序
  * 基本思想:在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。即:每当两相邻的数比较后发现它们的排序与排序要求相反时,就将它们互换。
  */
 public void bubbleSort(int[] array) {
     int temp;
     for(int i=0;i<array.length;i++){//趟数
       for(int j=0;j<array.length-i-1;j++){//比较次数
         if(array[j]>array[j+1]){
           temp=array[j];
           array[j]=array[j+1];
           array[j+1]=temp;
         }
       }
     }
    }

 /**
  * 快速排序
  * 基本思想:选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描,将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。
  * @param array
  */
 public void qsort(int array[]){
  if(array.length>1){
   _qsort(array,0,array.length-1);
  }
 }
 /**
  * 一趟快速排序
  * @param array
  */
 private void _qsort(int[] array,int low,int high){
  if(low < high){
   int middle = getMiddle(array, low, high);
   _qsort(array,low,middle-1);
   _qsort(array, middle+1, high);
  }
 }
 /**
  * 得到中间值
  */
 private int getMiddle(int[] array,int low,int high){
  int tmp = array[low];
  while(low < high){
   while(low < high && array[high] >= tmp)
    high--;
   array[low] = array[high];
   while(low<high && array[low]<=tmp)
    low++;
   array[high] = array[low];
  }
  array[low] = tmp;
  return low;
 }

 /**
  * 简单选择排序
  * 基本思想:在要排序的一组数中,选出最小的一个数与第一个位置的数交换;然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止。
  * @param array
  */
 public void selectSort(int[] array){
  int position=0;  
        for(int i=0;i<array.length;i++){  

            int j=i+1;  
            position=i;  
            int temp=array[i];  
            for(;j<array.length;j++){  
            if(array[j]<temp){  
                temp=array[j];  
                position=j;  
            }  
            }  
            array[position]=array[i];  
            array[i]=temp;  
        } 
 }

 /**
  * 希尔排序(最小增量排序)
  * 基本思想:算法先将要排序的一组数按某个增量d(n/2,n为要排序数的个数)分成若干组,每组中记录的下标相差d.对每组中全部元素进行直接插入排序,然后再用一个较小的增量(d/2)对它进行分组,在每组中再进行直接插入排序。当增量减到1时,进行直接插入排序后,排序完成。
  * @param array
  */
 public  void shellSort(int[] array){  
     double d1=array.length;  
     int temp=0;  
     while(true){  
         d1= Math.ceil(d1/2);  
         int d=(int) d1;  
         for(int x=0;x<d;x++){  
             for(int i=x+d;i<array.length;i+=d){  
                 int j=i-d;  
                 temp=array[i];  
                 for(;j>=0&&temp<array[j];j-=d){  
                  array[j+d]=array[j];  
                 }  
                 array[j+d]=temp;  
             }  
         }  
         if(d==1)  
             break;  
     }  
 }  

 /**
  * 打印数组中的所有元素
  */

 public void printArray(int[] array){
  for (int i = 0; i < array.length; i++) {
   System.out.print(array[i]+" ");
  }
 }
}



下面是几种排序方法分开使用的示例

利用Arrays带有的排序方法快速排序

复制代码代码如下:

import java.util.Arrays;
public class Test2{
        public static void main(String[] args){
                int[] a={5,4,2,4,9,1};
                Arrays.sort(a);  //进行排序
                for(int i: a){
                        System.out.print(i);
                }
        }
}

 

冒泡排序算法

复制代码代码如下:

public static int[] bubbleSort(int[] args){//冒泡排序算法
                for(int i=0;i<args.length-1;i++){
                        for(int j=i+1;j<args.length;j++){
                                if (args[i]>args[j]){
                                        int temp=args[i];
                                        args[i]=args[j];
                                        args[j]=temp;
                                }
                        }
                }
                return args;
        }

 

选择排序算法

复制代码代码如下:

public static int[] selectSort(int[] args){//选择排序算法
                for (int i=0;i<args.length-1 ;i++ ){
                        int min=i;
                        for (int j=i+1;j<args.length ;j++ ){
                                if (args[min]>args[j]){
                                        min=j;
                                }
                        }
                        if (min!=i){
                        int temp=args[i];
                        args[i]=args[min];
                        args[min]=temp;        
                        }
                }
                return args;
        }

 

插入排序算法

复制代码代码如下:

public static int[] insertSort(int[] args){//插入排序算法
                for(int i=1;i<args.length;i++){
                        for(int j=i;j>0;j--){
                                if (args[j]<args[j-1]){
                                        int temp=args[j-1];
                                        args[j-1]=args[j];
                                        args[j]=temp;        
                                }else break;
                        }
                }
                return args;
        }

 

以上就是java中的四种排序方法。不同的方法效率不一样,下面是不同的算法的比较和数据交换时的大O表示。

冒泡排序:比较O(N2) 数据交换O(N2)

选择排序:比较O(N2) 数据交换O(N)

插入排序:比较O(N2) 复制数据O(N)

在实际应用中,我们要尽量选择效率高的算法。