排序

Posted by DeepBlue on 12-05,2020

复习一下各个排序的代码,加深理解。

首先看一下各个排序算法的时间复杂度:

image-20200915204407956

冒泡排序(Bubble Sort)

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

public static void bubbleSort(int[] nums) {
    for (int i = 0; i < nums.length - 1; i++) {
        for (int j = 0; j < nums.length - 1 -i; j++) {
            if (nums[j] > nums[j + 1]) {
                int temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
            }
        }
    }
}

复杂度:

平均:$O(n2)$ 最好 :$O(n)$ 最坏:$O(n2)$ 稳定性:稳定

选择排序(Selection Sort)

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

public static void selectionSort(int[] nums) {
    for (int i = 0; i < nums.length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] < nums[minIndex]) {
                minIndex = j;
            }
        }
        int temp= nums[minIndex];
        nums[minIndex]=nums[i];
        nums[i]=temp;
    }
}

平均:$O(n2)$ 最好 :$O(n2)$ 最坏:$O(n^2)$ 稳定性:不稳定

插入排序(Insertion Sort)

插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

public static void insertionSort(int[] nums) {
    int preIndex, now;
    for (int i = 1; i < nums.length; i++) {
        preIndex = i - 1;
        now = nums[i];
        while (preIndex >= 0 && nums[preIndex] > now) {
            nums[preIndex + 1] = nums[preIndex];
            preIndex--;
        }
        nums[preIndex+1] = now;
    }

}

平均:$O(n2)$ 最好 :$O(n)$ 最坏:$O(n2)$ 稳定性:稳定

希尔排序(Shell Sort)

1959年Shell发明,第一个突破O(n2)的排序算法,是简单插入排序的改进版。它与插入排序的不同之处在于,它会优先比较距离较远的元素。希尔排序又叫缩小增量排序

算法描述:

  • 选择一个增量序列t1,t2,…,tk,其中ti>tj,tk=1;
  • 按增量序列个数k,对序列进行k 趟排序;
  • 每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序。仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。
public static void shellSort(int[] nums) {
    for (int step = nums.length / 2; step > 0; step /= 2) {
        //先分组,组数每次变为原来的1/2
        for (int i = step; i < nums.length; i++) {
            //从增量那组进行插入排序,直到完毕
            int j = i;
            int temp = nums[j];
            while (j-step>=0&&nums[j-step]>temp){
                nums[j]= nums[j-step];
                j=j-step;
            }
            nums[j]=temp;
        }
    }
}

快速排序(Quick Sort)

快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

public static void quickSort(int[] nums) {
    quickSortSub(nums, 0, nums.length - 1);
}

public static void quickSortSub(int[] nums, int start, int end) {
    if (start > end) {
        return;
    }
    int i = start;
    int j = end;
    int benchmark = nums[i];
    int temp;
    while (i < j) {
        while (i < j && benchmark <= nums[j]) {
            j--;
        }
        while (i < j && benchmark >= nums[i]) {
            i++;
        }
        temp = nums[j];
        nums[j] = nums[i];
        nums[i] = temp;
    }
    nums[start]= nums[i];
    nums[i]=benchmark;
    quickSortSub(nums,start,i-1);
    quickSortSub(nums,i+1,end);
}

平均:$O(nlog_2n)$ 最好 :$O(nlog_2n)$ 最坏:$O(n^2)$ 稳定性:不稳定

归并排序(Merge Sort)

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。

public static void mergeSort(int[] nums) {
    int[] temp = new int[nums.length];
    sort(nums, 0, nums.length - 1, temp);
}

public static void sort(int[] nums, int left, int right, int[] temp) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        sort(nums, 0, mid, temp);
        sort(nums, mid + 1, right, temp);
        merge(nums, left, mid, right, temp);
    }
}

public static void merge(int[] nums, int left, int mid, int right, int[] temp) {
    //左序列指针
    int i = left;
    //右序列指针
    int j = mid + 1;
    //temp指针
    int t = 0;
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            temp[t++] = nums[i++];
        } else {
            temp[t++] = nums[j++];
        }
    }
    while (i <= mid) {
        temp[t++] = nums[i++];
    }
    while (j <= right) {
        temp[t++] = nums[j++];
    }
    t=0;
    while(left <= right){
        nums[left++] = temp[t++];
    }
}

平均:$O(nlog_2n)$ 最好 :$O(nlog_2n)$ 最坏:$O(nlog_2n)$ 稳定性:稳定

堆排序(Heap Sort)

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

public static void heapSort(int[] nums) {
    for (int i = nums.length / 2 - 1; i >= 0; i--) {
        //从第一个非叶子结点从下至上,从右至左调整结构
        adjustHeap(nums, i, nums.length);
    }
    for (int i = nums.length - 1; i >= 0; i--) {
        //将堆顶元素与末尾元素进行交换
        swap(nums, 0, i);
        //重新调整
        adjustHeap(nums, 0, i);
    }
}

public static void adjustHeap(int[] nums, int i, int len) {
    int temp = nums[i];
    //从i结点的左子结点开始,也就是2i+1处开始
    for (int k = i * 2 + 1; k < len; k = k * 2 + 1) {
        //如果左子结点小于右子结点,k指向右子结点
        if (k + 1 < len && nums[k] < nums[k + 1]) {
            k++;
        }
        //如果子节点大于父节点,将子节点值赋给父节点(不用进行交换)
        if (nums[k] > temp) {
            nums[i] = nums[k];
            i = k;
        } else {
            break;
        }
    }
    nums[i]=temp;
}

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

平均:$O(nlog_2n)$ 最好 :$O(nlog_2n)$ 最坏:$O(nlog_2n)$ 稳定性:不稳定

本文就是笔者关于排序算法的一次记录,以便加深理解,如果需要详细了解具体的排序算法,请参考其他博主对这些排序算法的讲解,如果有好的建议,希望大家指出!