首页 > 编程语言 > 详细

常见排序算法

时间：2021-05-24 00:50:38      阅读：47      评论：0      收藏：0      [点我收藏+]

1、冒泡排序

 /**
     * 冒泡排序（按从小到大排序）
     * 最佳情况：T(n) = O(n)   最差情况：T(n) = O(n2)   平均情况：T(n) = O(n2)
     */
    @Test
    public void bubbleSort() {
        int[] array = { 3, 4, 6, 1, 8, 2, 1, 5, 9, 0 };
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j + 1] < array[j]) {
                    int temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                }
            }
        }
        for (int i : array) {
            System.out.print(i);
            System.out.print(" ");
        }
    }

技术分享图片
    /**
     * 冒泡排序（按从小到大排序）
     * 最佳情况：T(n) = O(n)   最差情况：T(n) = O(n2)   平均情况：T(n) = O(n2)
     */
    @Test
    public void bubbleSort() {
        int[] array = { 3, 4, 6, 1, 8, 2, 1, 5, 9, 0 };
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j + 1] < array[j]) {
                    int temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                }
            }
        }
        for (int i : array) {
            System.out.print(i);
            System.out.print(" ");
        }
    }
技术分享图片

2、选择排序

 /**
     * 选择排序（按从小到大排序）
     * 最佳情况：T(n) = O(n2) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)
     */
    @Test
    public void selectionSort() {
        int[] array = { 3, 4, 6, 1, 8, 2, 1, 5, 9, 0 };
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i; j < array.length; j++) {
                if (array[j] < array[minIndex])
                    minIndex = j;
            }
            int temp = array[minIndex];
            array[minIndex] = array[i];
            array[i] = temp;
        }
        for (int i : array) {
            System.out.print(i);
            System.out.print(" ");
        }
    }

技术分享图片
    /**
     * 选择排序（按从小到大排序）
     * 最佳情况：T(n) = O(n2) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)
     */
    @Test
    public void selectionSort() {
        int[] array = { 3, 4, 6, 1, 8, 2, 1, 5, 9, 0 };
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i; j < array.length; j++) {
                if (array[j] < array[minIndex])
                    minIndex = j;
            }
            int temp = array[minIndex];
            array[minIndex] = array[i];
            array[i] = temp;
        }
        for (int i : array) {
            System.out.print(i);
            System.out.print(" ");
        }
    }
技术分享图片

3、插入排序

 /**
     * 插入排序（按从小到大排序）
     * 最佳情况：T(n) = O(n) 最坏情况：T(n) = O(n2) 平均情况：T(n) = O(n2)
     */
    @Test
    public void insertionSort() {
        int[] array = { 3, 4, 6, 1, 8, 2, 1, 5, 9, 0 };
        int current;
        for (int i = 0; i < array.length - 1; i++) {
            current = array[i + 1];
            int preIndex = i;
            while (preIndex >= 0 && current < array[preIndex]) {
                array[preIndex + 1] = array[preIndex];
                preIndex--;
            }
            array[preIndex + 1] = current;
        }
        for (int i : array) {
            System.out.print(i);
            System.out.print(" ");
        }
    }

技术分享图片
    /**
     * 插入排序（按从小到大排序）
     * 最佳情况：T(n) = O(n) 最坏情况：T(n) = O(n2) 平均情况：T(n) = O(n2)
     */
    @Test
    public void insertionSort() {
        int[] array = { 3, 4, 6, 1, 8, 2, 1, 5, 9, 0 };
        int current;
        for (int i = 0; i < array.length - 1; i++) {
            current = array[i + 1];
            int preIndex = i;
            while (preIndex >= 0 && current < array[preIndex]) {
                array[preIndex + 1] = array[preIndex];
                preIndex--;
            }
            array[preIndex + 1] = current;
        }
        for (int i : array) {
            System.out.print(i);
            System.out.print(" ");
        }
    }
技术分享图片

4、希尔排序 

 /**
     * 从大到小
     * @param array
     */
    public static void shellSort1(int[] array) {
        int number = array.length/2;
        int i,j,temp;
        while (number >= 1){
            for (i = number; i < array.length; i++) {
                temp = array[i];
                j = i - number;
                while (j >= 0 && array[j] < temp) {
                    array[j + number] = array[j];
                    j = j - number;
                }
                array[j + number] = temp;
            }
            number = number/2;
        }
    }

 


技术分享图片
    /**
     * 从大到小
     * @param array
     */
    public static void shellSort1(int[] array) {
        int number = array.length/2;
        int i,j,temp;
        while (number >= 1){
            for (i = number; i < array.length; i++) {
                temp = array[i];
                j = i - number;
                while (j >= 0 && array[j] < temp) {
                    array[j + number] = array[j];
                    j = j - number;
                }
                array[j + number] = temp;
            }
            number = number/2;
        }
    }
技术分享图片

5、归并排序 

 /**
     * 从小到大排序
     * @param arr
     */
    public static void sort(int []array){
        int []temp = new int[array.length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        sort(array,0,array.length-1,temp);
    }
    private static void sort(int[] array,int left,int right,int []temp){
        if(left<right){
            int mid = (left+right)/2;
            sort(array,left,mid,temp);// 左边归并排序，使得左子序列有序
            sort(array,mid+1,right,temp);// 右边归并排序，使得右子序列有序
            merge(array,left,mid,right,temp);// 将两个有序子数组合并操作
        }
    }
    private static void merge(int[] arr,int left,int mid,int right,int[] temp){
        int i = left;// 左序列指针
        int j = mid + 1;// 右序列指针
        int t = 0;// 临时数组指针
        while (i <= mid && j <= right){
            if(arr[i] <= arr[j]){
                temp[t++] = arr[i++];
            }else {
                temp[t++] = arr[j++];
            }
        }
        while(i <= mid){// 将左边剩余元素填充进temp中
            temp[t++] = arr[i++];
        }
        while(j <= right){// 将右序列剩余元素填充进temp中
            temp[t++] = arr[j++];
        }
        t = 0;
        // 将temp中的元素全部拷贝到原数组中
        while(left <= right){
            arr[left++] = temp[t++];
        }
    }

技术分享图片
    /**
     * 从小到大排序
     * @param arr
     */
    public static void sort(int []array){
        int []temp = new int[array.length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        sort(array,0,array.length-1,temp);
    }
    private static void sort(int[] array,int left,int right,int []temp){
        if(left<right){
            int mid = (left+right)/2;
            sort(array,left,mid,temp);// 左边归并排序，使得左子序列有序
            sort(array,mid+1,right,temp);// 右边归并排序，使得右子序列有序
            merge(array,left,mid,right,temp);// 将两个有序子数组合并操作
        }
    }
    private static void merge(int[] arr,int left,int mid,int right,int[] temp){
        int i = left;// 左序列指针
        int j = mid + 1;// 右序列指针
        int t = 0;// 临时数组指针
        while (i <= mid && j <= right){
            if(arr[i] <= arr[j]){
                temp[t++] = arr[i++];
            }else {
                temp[t++] = arr[j++];
            }
        }
        while(i <= mid){// 将左边剩余元素填充进temp中
            temp[t++] = arr[i++];
        }
        while(j <= right){// 将右序列剩余元素填充进temp中
            temp[t++] = arr[j++];
        }
        t = 0;
        // 将temp中的元素全部拷贝到原数组中
        while(left <= right){
            arr[left++] = temp[t++];
        }
    }
技术分享图片

 6、快速排序 

 public static void main(String[] args) {
        int[] array = new int[]{2,3,5,6,9,1,0,3,4,6};
        quickSort(array);
        for (int i=0;i<array.length;i++) {
            System.out.print(array[i] + " ");
        }
    }

    /**
     * 快速排序，使得整数数组 arr 有序
     */
    public static void quickSort(int[] array) {
        if (array == null || array.length < 2) {
            return;
        }
        quickSort(array, 0, array.length - 1);
    }

    /**
     * 快速排序，使得整数数组 arr 的 [L, R] 部分有序
     */
    public static void quickSort(int[] arr, int L, int R) {
        if(L < R) {
            // 把数组中随机的一个元素与最后一个元素交换，这样以最后一个元素作为基准值实际上就是以数组中随机的一个元素作为基准值
            swap(arr, new Random().nextInt(R - L + 1) + L, R);
            int[] p = partition(arr, L, R);
            quickSort(arr, L, p[0] - 1);
            quickSort(arr, p[1] + 1, R);
        }
    }

    /**
     * 分区的过程，整数数组 arr 的[L, R]部分上，使得：
     *   大于 arr[R] 的元素位于[L, R]部分的右边，但这部分数据不一定有序
     *   小于 arr[R] 的元素位于[L, R]部分的左边，但这部分数据不一定有序
     *   等于 arr[R] 的元素位于[L, R]部分的中间
     * 返回等于部分的第一个元素的下标和最后一个下标组成的整数数组
     */
    public static int[] partition(int[] arr, int L, int R) {

        int basic = arr[R];
        int less = L - 1;
        int more = R + 1;
        while(L < more) {
            if(arr[L] < basic) {
                swap(arr, ++less, L++);
            } else if (arr[L] > basic) {
                swap(arr, --more, L);
            } else {
                L++;
            }
        }

        return new int[] { less + 1, more - 1 };

    }

    /*
     * 交换数组 arr 中下标为 i 和下标为 j 位置的元素
     */
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

7、堆排序

 

8、计数排序

 

9、桶排序

 

10、基数排序

 

递归

1、递归算法计算n!

  /**
     * 递归算法
     */
    @Test
    public void recursion() {
        System.out.println(factorial(2));
    }

    /**
     * 递归算法计算阶乘n!
     * 
     * @param n
     * @return
     */
    public static Integer factorial(Integer n) {
        if (n < 0)
            return 0;
        if (n == 1)
            return 1;
        return n * factorial(n - 1);
    }

 2、递归计算1*2+2*3+3*4+...+n*(n+1)

 /**
     * 递归算法
     */
    @Test
    public void recursion() {
        System.out.println(productSum(4));
    }

    /**
     * 递归算法计算1*2+2*3+3*4+...+n*(n+1)
     * @param n
     * @return
     */
    public static Integer productSum(Integer n) {
        if (n <= 0)
            return 0;
        if (n == 1)
            return 2;
        int result = productSum(n - 1) + n * (n + 1);
        return result;
    }
技术分享图片
    /**
     * 递归算法
     */
    @Test
    public void recursion() {
        System.out.println(productSum(4));
    }

    /**
     * 递归算法计算1*2+2*3+3*4+...+n*(n+1)
     * @param n
     * @return
     */
    public static Integer productSum(Integer n) {
        if (n <= 0)
            return 0;
        if (n == 1)
            return 2;
        int result = productSum(n - 1) + n * (n + 1);
        return result;
    }
技术分享图片
 
 

 

常见排序算法

原文：https://www.cnblogs.com/wffzk/p/14802622.html
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！