Java教程

排序算法

本文主要是介绍排序算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

1.排序分类

 

 

2.时间\空间复杂度

图片来自:https://www.cnblogs.com/onepixel/articles/7674659.html

原图的快排的空间复杂度错误

 

 

 

3. 具体实现

tips: 按升序排序

3.1 插入排序

1)直接插入排序

思路

  • 1 在有序队列 [0, j] 中插入 [i] 元素
  • 2.1 若 [i] < [j] 则移动元素 [j] 到相邻的下一个位置 j + 1
  • 2.2 若 [i] > [j] 则将 [i] 元素插入到位置 j + 1
  • 如此反复

复杂度

  • 时间复杂度:O(n2)
  • 空间复杂度:O(1)
public class InsertSort {
    private static void insertSort(int[] nums) {
        for (int i=1; i<nums.length; i++) {
            int j = i - 1;
            int cur = nums[i];
            while (j >= 0 && nums[j] > cur) {
                nums[j+1] = nums[j];
                j--;
            }
            nums[j + 1] = cur;
        }
    }
}

 

2)希尔排序

思路:是一种特殊的插入排序,其根据不同的步长更新成最终的有序序列

public class S4_ShellSort {

    private static void shellSort(int[] nums) {
        for (int i=(int)Math.floor(nums.length); i>0; i=(int)Math.floor(i/2)) {
            insertSort(nums, i);
        }
    }

    private static void insertSort(int[] nums, int len) {
        for (int i=len; i<nums.length; i++) {
            int j = i - len;
            int cur = nums[i];
            while (j >= 0 && cur < nums[j]) {
                nums[j + len] = nums[j];
                j = j - len;
            }
            nums[j + len] = cur;
        }
    }
}

 

 

3.2 交换排序

1)冒泡排序

思路:在一趟排序中,若[i] < [j],交换两个元素,否则继续向下走。一趟排序结束后,最大关键字被交换到了最后固定位置。如此反复多趟,直到在某一趟一次交换也不发生,排序结束

复杂度:

  • 时间复杂度:O(n2)
  • 空间复杂度:O(1)
public class BubbleSort {

    private static void bubbleSort(int[] nums) {
        boolean flag = true;
        for (int i=0; flag; i++) {
            flag = false;
            // 若未发生交换则已经排好序
            for (int j=nums.length-1; j>=1; j--) {
                if (nums[j] < nums[j-1]) {
                    swap(nums, j, j-1);
                    flag = true;
                }
            }
        }
    }

    private static void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

 

2)快速排序

思路:根据分割函数,确定分割数字的最终位置,分成左右两侧。左侧 <=【分割数字】,【分割数字】 <= 右侧。递归执行

复杂度:

  • 时间复杂度:O(nlogn)
  • 空间复杂度:O(logn)

代码1

public class S2_QuickSort {

    private static void quickSort(int [] nums, int l, int r) {
        if (l < r) {
            int mid = partition(nums, l, r);
            quickSort(nums, l, mid - 1);
            quickSort(nums, mid+1, r);
        }
    }

    private static int partition(int[] nums, int l, int r) {
        int flag = nums[r];
        while (l < r) {
            while (l < r && nums[l] < flag) l++;
            if (l < r) nums[r--] = nums[l];
            while (l < r && nums[r] > flag) r--;
            if (l < r) nums[l++] = nums[r];
        }
        nums[l] = flag;
        return l;
    }
}

 

代码2

public class S2_QuickSort2 {

    private static void quickSort(int [] nums, int l, int r) {
        if (l < r) {
            int mid = partition(nums, l, r);
            quickSort(nums, l, mid - 1);
            quickSort(nums, mid+1, r);
        }
    }

    private static int partition(int[] nums, int l, int r) {
        int flag = nums[r];
        int i = l - 1; // i指向的位置是分割左侧的最后一个位置
        for (int j=l; j<r; j++) {
            if (nums[j] < flag) {
                i = i + 1;
                swap(nums, i, j);
            }
        }
        swap(nums, i + 1, r);
        return i + 1;
    }

    private static void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

 

 

3.3 选择排序

1)简单选择排序

思路:从头到尾在无序序列找到最小关键字,和无序序列第一个元素进行交换。如此反复,直至排序结束

复杂度:

  • 时间复杂度:O(n2)
  • 空间复杂度:O(1)
public class SelectSort {

    private static void selectSort(int[] nums) {
        for (int i=0; i<nums.length-1; i++) {
            int minj = i;
            for (int j=i; j<nums.length; j++) {
                if (nums[j] < nums[minj]) minj = j;
            }
            int t = nums[i]; nums[i] = nums[minj]; nums[minj] = t;
        }
    }
}

 

2)堆排序

思路:

  • 构建最大堆(存储形式:数组)
  • 将头部最大元素与尾部元素交换,将除尾部以外的元素堆堆化调整最大堆(此次堆化,有头节点开始向下堆化即可)
  • 如此反复上述步骤

复杂度:

  • 时间复杂度:O(nlogn) 
    • 堆化:O(logn)
    • 交换n次
  • 空间复杂度:O(1)
public class HeapSort {

    private static void heapSort(int[] nums) {
        int n = nums.length - 1;

        // 堆化成大根堆
        for (int i=n/2; i>=0; i--) {
            heapify(nums, n, i);
            // System.out.println(nums[0]);
        }

        while (n > 0) {
            // 排序 选取关键字
            swap(nums, 0, n);
            n--;
            // 堆化
            heapify(nums, n, 0);
        }
    }

    // 建立大根堆
    private static void heapify(int[] nums, int n, int i) {
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        int t = i;
        if (l <= n && nums[l] > nums[t]) t = l;
        if (r <= n && nums[r] > nums[t]) t = r;
        if (t != i) {
            swap(nums, t, i);
            heapify(nums, n, t);
        }
    }

    private static void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

 

 

3.4 归并排序

1)二路归并排序

思路:递归分割为多个有序数组,后合并为一个有序数组

复杂度:

  • 时间复杂度:O(nlogn)
  • 空间复杂度:O(n)
public class MergeSort {

    private static void mergeSort(int[] nums, int l, int r) {
        if (l >= r) return ;
        int mid = l + r >> 1;
        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);
        merge(nums, l, mid, r);
    }

    private static void merge(int[] nums, int l, int mid, int r) {
        int[] tmp = new int[r - l + 1];
        int i1 = l;
        int i2 = mid + 1;
        int idx = 0;
        while (i1 <= mid && i2 <= r) {
            if (nums[i1] < nums[i2]) tmp[idx++] = nums[i1++];
            else tmp[idx++] = nums[i2++];
        }
        while (i1 <= mid) tmp[idx++] = nums[i1++];
        while (i2 <= r) tmp[idx++] = nums[i2++];
        for (int j=l, j1=0; j<=r; j++) nums[j] = tmp[j1++];
    }
}

 

 

3.5 基数排序

 思路:多关键字排序

 

3.6 计数排序

思路:

  • 记录所有数组元素出现的次数在数组C
  • 求其数组C的前缀和,(求前缀和的目的是放置元素的对应位置)
  • 放置元素是从某一组元素的最后一个位置开始放置,(如:C[1] = 3,那么 B[3] = 1, B[2] = 1, B[1] = 1)
  • 恢复元素到原有数组,(因为B数组元素从1开始)
public class CountSort {
    private static int NMAX = 1000; // 数字最大值

    private static void countSort(int[] nums) {
        int n = nums.length;
        int[] C = new int[NMAX + 1];
        int[] B = new int[n + 1];

        for (int i=0; i<n; i++) C[nums[i]]++;
        for (int i=1; i<=NMAX; i++) C[i] = C[i] + C[i-1];

        for (int i=0; i<n; i++) {
            B[C[nums[i]]] = nums[i];
            C[nums[i]]--;
        }

        // System.out.println(Arrays.toString(B));
        for (int i=1; i<=n; i++) nums[i - 1] = B[i];
    }
}

 

 

参考链接:

https://www.cnblogs.com/onepixel/articles/7674659.html

这篇关于排序算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!