公司简介 新闻中心 案例中心 联系我们

java实现常见排序算法

    时间：2018-10-09

【转载】

java实现常见排序算法 

java实现常见排序算法，算法详解请参见常见排序算法。 

本文实现的排序算法分别为冒泡排序（鸡尾酒排序）、选择排序、插入排序（二分插入排序、希尔插入排序）、归并排序、堆排序、快速排序等九种排序算法。

实现代码 

1、冒泡排序+鸡尾酒排序

import java.util.Arrays;

/**

 * 冒泡排序算法+鸡尾酒排序法

 * @author Misui_user

 *

 */

public class BubbleSort {

    /**

     * @param args

     */

    public static void main(String[] args) {

        // TODO Auto-generated method stub

        int[] test={8,56,29,7,1,5,6};

        int[] test2={8,56,29,7,1,5,6};

        bubble(test);

        cocktail(test2);

        System.out.println(Arrays.toString(test));

        System.out.println(Arrays.toString(test2));

    }

    /**

     * 交换数组对应位置的元素

     * @param array

     * @param m

     * @param n

     */

    private static void swap(int[] array,int m,int n){

        int temp=array[m];

        array[m]=array[n];

        array[n]=temp;

    }

    /**

     * 冒泡法排序方法

     * @param array

     * @return

     */

    public  static void bubble(int[] array){

        for(int i=array.length-1;i>=0;i--){

            for(int j=0;j<i;j++){

                if(array[j]>array[j+1]){

                    swap(array,j,j+1);

                }

            }

        }

    }

    /**

     * 鸡尾酒排序方法

     * @param array

     * @return

     */

    public static void cocktail(int[] array){

        int right=0;

        int left=array.length-1;

        while(right<=left){

            for(int i=right;i<left;i++){

                if(array[i]>array[i+1]){

                    swap(array,i,i+1);

                }

            }

            for(int i=left;i>right;i--){

                if(array[i]<array[i-1]){

                    swap(array,i,i-1);

                }

            }

            right++;

            left--;

        }

    }

}

2、选择排序

import java.util.Arrays;

/**

 * 选择排序

 * @author Misui_user

 *

 */

public class SelectionSort {

    /**

     * @param args

     */

    public static void main(String[] args) {

        // TODO Auto-generated method stub

        int[] test={8,56,29,7,1,5,6};

//      int[] test2={8,56,29,7,1,5,6};

        selection(test);

        System.out.println(Arrays.toString(test));

//      System.out.println(Arrays.toString(test2));

    }

    /**

     * 交换数组中对应位置的元素

     * @param array

     * @param m

     * @param n

     */

    private static void swap(int[] array,int m,int n){

        int temp=array[m];

        array[m]=array[n];

        array[n]=temp;

    }

    /**

     * 选择排序方法

     * @param array

     * @return

     */

    public static void selection(int[] array){

        for(int i=array.length-1;i>0;i--){

            int max=0;

            for(int j=0;j<=i;j++){

                if(array[max]<array[j]){

                    max=j;

                }

            }

            swap(array,max,i);

        }

    }

}

3、插入排序+二分法排序+希尔排序

import java.util.Arrays;

/**

 * 

 * 插入排序

 * @author Misui_user

 *

 */

public class InsertionSort {

    /**

     * @param args

     */

    public static void main(String[] args) {

        // TODO Auto-generated method stub

        int[] test={8,56,29,7,1,5,6};

//      insertion(test);

//      halfInsertion(test);

        shell(test);

        System.out.println(Arrays.toString(test));

    }

    /**

     * 插入排序方法

     * @param array

     * @return

     */

    public static void insertion(int[] array){

        if(array.length<2) return;

        for(int i=1;i<array.length;i++){

            int get=array[i];

            int j=i-1;

            while(j>=0&&get<array[j]){

                array[j+1]=array[j];

                j--;

            }

            array[j+1]=get;

        }

    }

    /**

     * 二分查找插入排序

     * @param array

     */

    public static void halfInsertion(int[] array){

        if(array.length<2) return;

        for(int i=1;i<array.length;i++){

            int get=array[i];

            int right=i-1,left=0;

            while(left<=right){                 //二分法查找位置

                int mid=(left+right)/2;

                if(array[mid]>get){

                    right=mid-1;

                }else{

                    left=mid+1;

                }

            }

            for(int j=i-1;j>=left;j--){

                array[j+1]=array[j];

            }

            array[left]=get;

        }

    }

    /**

     * shell排序方法

     * @param array

     */

    public static void shell(int[] array){

        int h=array.length/2;

        while(h>=1){

            for(int i=h;i<array.length;i++){

                int get=array[i];

                int j=i-h;

                while(j>=0&&array[j]>get){

                    array[j+h]=array[j];

                    j=j-h;

                }

                array[j+h]=get;

            }

            h=h/2;

        }

    }

}

4、归并排序

import java.util.Arrays;

/**

 * 并归排序

 * @author Misui_user

 *

 */

public class MergeSort {

    /**

     * @param args

     */

    public static void main(String[] args) {

        // TODO Auto-generated method stub

        int[] test={8,56,29,7,1,5,6};

        mergeSort(test);

        System.out.println(Arrays.toString(test));

    }

    /**

     * 将已排序好的序列合并成为一个序列

     * @param array

     * @param left

     * @param mid

     * @param right

     */

    private static void merge(int[] array,int left,int mid,int right){

        int[] mergearray=new int[right-left+1];

        int i=left,j=mid+1,index=0;

        while(i<=mid&&j<=right){

            if(array[i]<=array[j]){

                mergearray[index]=array[i];

                i++;

                index++;

            }

            else{

                mergearray[index]=array[j];

                j++;

                index++;

            }

        }

        while(i<=mid){

            mergearray[index++]=array[i++];

        }

        while(j<=right){

            mergearray[index++]=array[j++];

        }

        for(int k=0;k<mergearray.length;k++){

            array[left+k]=mergearray[k];

        }

    }

    /**

     * 采用递归的方式实现归并排序

     * @param array

     * @param left

     * @param right

     */

    private static void mergeS(int[] array,int left,int right){

        if (left == right)    // 当待排序的序列长度为1时，递归开始回溯，进行merge操作

            return;

        int mid = (left + right) / 2;

        mergeS(array, left, mid);

        mergeS(array, mid + 1, right);

        merge(array, left, mid, right);

    }

    public static void mergeSort(int[] array){

        mergeS(array, 0, array.length-1);

    }

}

5、堆排序

import java.util.Arrays;

/**

 * 堆排序

 * @author Misui_user

 *

 */

public class HeapSort {

    /**

     * @param args

     */

    public static void main(String[] args) {

        // TODO Auto-generated method stub

        int[] test={8,56,29,7,1,5,6};

        heap(test);

        System.out.println(Arrays.toString(test));

    }

    /**

     * 交换数组内指定位置的两个元素

     * @param array

     * @param m

     * @param n

     */

    private static void swap(int[] array,int m,int n){

        int temp=array[m];

        array[m]=array[n];

        array[n]=temp;

    }

    /**

     * 从i从向下进行堆调整

     * @param array

     */

    private static void adjustHeap(int[] array,int i,int size){

        int left=2*i+1;         //左子节点索引

        int right=2*i+2;        //右子节点索引

        int max=i;

        if(left<size&&array[left]>array[max]){

            max=left;

        }

        if(right<size&&array[right]>array[max]){

            max=right;

        }

        if(max!=i){

            swap(array,max,i);

            adjustHeap(array,max,size);

        }

    }

    public static void heap(int[] array){

        int size=array.length;

        for(int i=(size/2-1);i>=0;i--){     //构建大顶堆

            adjustHeap(array,i,size);

        }

        while(size>1){

            swap(array,--size,0);

            adjustHeap(array,0,size);

        }

    }

}

6、快速排序

import java.util.Arrays;

/**

 * 快速排序

 * @author Misui_user

 *

 */

public class QuickSort {

    /**

     * @param args

     */

    public static void main(String[] args) {

        // TODO Auto-generated method stub

        int[] test={8,56,29,7,1,5,6};

        quick(test);

        System.out.println(Arrays.toString(test));

    }

    /**

     * 交换数组中对应位置的元素

     * @param array

     * @param m

     * @param n

     */

    private static void swap(int[] array,int m,int n){

        int get=array[m];

        array[m]=array[n];

        array[n]=get;

    }

    /**

     * 快速排序方法

     * @param array

     */

    public static void quick(int[] array){

        int left=0,right=array.length-1;

        quickSort(array,left,right);

    }

    /**

     * 快排递归方法

     * @param array

     * @param left

     * @param right

     */

    private static void quickSort(int[] array,int left,int right){

        if(left>=right) return;

        int mid=sp(array,left,right);

        quickSort(array,left,mid-1);

        quickSort(array,mid+1,right);

    }

    /**

     * 将数组按照基准记性分列

     * @param array

     * @param left

     * @param right

     * @return

     */

    private static int split(int[] array,int left,int right){

        int pivot = array[right];               // 这里每次都选择最后一个元素作为基准

        int tail = left - 1;                // tail为小于基准的子数组最后一个元素的索引

        for (int i = left; i < right; i++)  // 遍历基准以外的其他元素

        {

            if (array[i] <= pivot)              // 把小于等于基准的元素放到前一个子数组末尾

            {

                swap(array, ++tail, i);

            }

        }

        swap(array, tail + 1, right);           // 最后把基准放到前一个子数组的后边，剩下的子数组既是大于基准的子数组

                                            // 该操作很有可能把后面元素的稳定性打乱，所以快速排序是不稳定的排序算法

        return tail + 1;                    // 返回基准的索引

    }

    /**

     * 采用直观的方式实现按基准分列

     * @param array

     * @param left

     * @param right

     * @return

     */

    private static int sp(int[] array,int left,int right){

        int mid=left;

        while(left<=right){

            if(mid==left){

                if(array[right]<array[mid]){

                    swap(array,mid,right);

                    mid=right;

                }else{

                    right--;

                }

                continue;

            }

            if(array[left]>array[mid]){

                swap(array,mid,left);

                mid=left;

            }else{

                left++;

            }

        }

        return mid;

    }

}

 

上一篇：企业的根本目标及其内涵（一）

下一篇：java反射机制&动态代理