数据结构：排序（基础）

比较 3 种简单排序

排序的本质是将数据按特定顺序排列，以便我们更轻松地使用这些数据。在本文中，我将讨论一些基本的排序算法：冒泡排序、选择排序和插入排序。

排序算法及其复杂性

算法	复杂
冒泡排序	O( ^n² )
选择排序	O( ^n² )
插入排序	O( ^n² )
希尔排序	O( ^n² )
快速排序	O( ^n² )
基数排序	O(nk)
堆排序	O(nlog(n))
合并排序	O(nlog(n))

在进入正文之前，我想推荐一个网站，它能帮助你直观地了解这些排序算法的工作原理。（PS：它也能帮助你了解其他内容，比如哈希表、二叉堆等等的可视化）。这个网站也很有用！

冒泡排序

在冒泡排序中，我们每次比较两个元素，然后交换它们或继续比较下一对。它的运行速度非常慢，但从概念上讲，它是最简单的排序算法。

对大小为n的数组进行排序的伪代码

1. Repeat i) to ii) for n times
    i) Compare the leftmost element in array with the next element
        a. If the leftmost element is bigger, swap them
        b. Else, go to 2.
    ii) Move to next position, set that element to be the leftmost element. Is there next element?
        a. Yes, go back to i)
        b. No, go back to 1.
2. Done

这是冒泡排序的 Java 代码

public void bubbleSort() {
    int out, in, temp;
    int[] a = new int[nElems];      // nElems is the number of elements we'll input later ^^||
    for(out=nElems-1; out>1; out--) {  
        for(in=0; in<out; in++) {
            if( a[in] > a[in+1] ) { // out of order?
                temp = a[in];       // swap them
                a[in] = a[in+1];
                a[in+1] = temp;
            }
        }
    }
}

冒泡排序的效率

比较操作：

对于 N 个项目： (N-1) + (N-2) + (N-3) + ... + 1
= N*(N-1)/2
≈ N ² /2
交换操作：

通常小于比较操作
≈ N ² /4
这意味着它的复杂度≈O(N2 ⁾，相当慢

选择排序

在选择排序中，我们沿着数据移动并选择最小项，将所选项交换到位置 0，依此类推。以下是大小为n 的数组的伪代码

1. Repeat i) to ii) for (n-1) rounds
    i) Go through every unsorted element
    ii) Pick the smallest one and swap with element at the first position (but next to those already been sorted)
2. Done

选择排序的 Java 代码

public void selectionSort() {
    int out, in, min, temp;
    int[] a = new int[nElems];        // nElems is the number of elements we'll input later ^^||
    for(out=0; out<nElems-1; out++) {
        min = out;
        for(in = out+1; in<nElems; in++) {
            if(a[in] < a[min]) {      // if min is greater,
                min = in;             // we have a new min
                temp = a[out];        // swap 'em
                a[out] = a[min];
                a[min] = temp;
            }
        }
    }
}

选择排序的效率

比较操作：

与冒泡排序相同
≈ N ² /2
交换操作：

通常小于 N
因此我们得到 O(N ² )；慢 :/

插入排序

我们将数据分成两个列表（已排序和未排序）。在每次迭代中，将未排序列表的第一个元素插入到已排序列表中的适当位置。伪代码

1. Repeat i) and ii) for (n-1) rounds
    i) insert the first unsorted element, to the sorted
    ii) compare the newly inserted element to all the sorted, and put it in place
2. Done

java代码！

public void insertionSort() {
    int in, out;
    int[] a = new int[nElems];         // nElems is the number of elements we'll input later ^^||
    for(out=1; out<nElems; out++) {    // out is dividing line
        long temp = a[out];            // remove marked item
        in = out;                      // start shifts at out
        while(in>0 && a[in-1]>=temp) { // until one is smaller,
            a[in] = a[in-1];           // shift item to right
            --in;                      // go left one position
        }
        a[in] = temp; // insert marked item
    }
}

选择排序的效率

比较操作：

^{N* (} N-1)/4≈N2
/ 4
复制操作：

通常类似于比较运算
其复杂度≈O(N2 ⁾；仍然很慢。
如果数据已排序，则该算法的运行时间几乎为 O(N)。
如果数据是反向排序，它的运行速度会非常慢，就像冒泡排序一样

比较 3 种简单排序

它们只需要初始数据数组加上一点额外的内存，但所有算法的执行时间都是 O(N ² )。

冒泡排序简单，但效率最低。如果数据量较小，则比较实用。
选择排序尽量减少交换次数，但比较次数仍然很高
插入排序是三者中最通用的，并且在大多数情况下是最好的，假设数据量很小或者数据几乎是排序的。

鏂囩珷鏉ユ簮锛�https://dev.to/rinsama77/data-struct-sorting-basic-1pkn