排序总结

柔情只为你懂 2022-10-02 12:47 149阅读 0赞

写一下关于排序算法的总结。排序是所有算法中最基础的，面试中有可能会手写排序算法，如果对排序算法不是很熟悉，在很短的时间内是写不出来的，所以，需要对排序算法特别的熟悉。

***1.冒泡排序***

冒泡排序思想：每次比较相邻的两个元素的大小，不满足我们给定的条件就交换，这样一趟下来，可以将数组中最大值或者最小值放到最后一个位置。最多进行n趟就能将数组排序。

冒泡排序算法是稳定算法。时间复杂度是![o(n^\{2\})][o_n_2]，空间复杂度为![o(1)][o_1]。

代码如下：

void bubblesort1(vector<int> &arr){
        size_t len = arr.size();
        for(int i = 0; i < len; i++){//进行len趟
            for(int j = 0; j < len - i - 1; j++){
                if(arr[j] < arr[j + 1])//如果小就交换，将最小的元素放到最后面
                    swap(arr[j], arr[j + 1]);
            }
        }
    }

可以将上面的代码进行改进，有时候并不需要对数组进行n趟，当数组已经排好序的时候就可以跳出第一个循环。我们根据每趟交换的次数来判断数组是否已经排序，如果交换的次数为0则证明已经排好序，可以跳出循环。下面是代码：

void bubblesort2(vector<int> &arr){
        size_t len = arr.size();
        bool flag = true;
        for(int i = 0; i < len; i++){
            flag = true;//加一个标志位，如果没有交换就表示排序完成，跳出循环
            for(int j = 0; j < len - i - 1; j++){
                if(arr[j] < arr[j + 1]){
                    swap(arr[j], arr[j + 1]);
                    flag = false;
                }
            }
            if(flag) break;
        }
    }

***2.插入排序***

插入排序的思想：从第二个元素开始，从后向前查找，找到适合该元素的位置，然后将该元素放在适合的位置中。

插入排序算法是稳定的，时间复杂度为![o(n^\{2\})][o_n_2]，空间复杂度为![o(1)][o_1]。

下面是代码：

void insertsort1(vector<int> &arr){
        size_t len = arr.size();
        int j;
        for(int i = 2; i < len; i++){
            j = i - 1;
            while(j >= 0 && arr[j] > arr[j + 1]){//通过交换将第i个数放到合适的位置
                swap(arr[j], arr[j + 1]);
                j--;
            }
        }
    }

上面是通过交换的方法将每个元素放到适合的位置，下面用赋值的方法从新写一下插入排序：

void insertsort2(vector<int> &arr){
        size_t len = arr.size();
        int tem;
        int j;
        for(int i = 0; i < len; i++){
            tem = arr[i];
            j = i;
            while(j > 0 && arr[j - 1] > tem){//找到第i个元素的位置，然后将第i个元素放上去
                arr[j] = arr[j - 1];
                j--;
            }
            arr[j] = tem;
        }
    }

***3.选择排序***

选择排序的思想： 从数组的N个数中选出最小或者最大的放在第一个位置，然后从剩下的N-1个数中选出最小的或者最大的放在第二个位置，这样N趟就能将数组排好序。

选择排序是不稳定排序，时间复杂度为![o(n^\{2\})][o_n_2]，空间复杂度为![o(1)][o_1]。

代码如下：

void choicesort(vector<int> &arr){
        size_t len = arr.size();
        for(int i = 0; i < len; i++){
            int index = i;
            int tem = arr[i];
            for(int j = i + 1; j < len; j++){
                if(arr[j] < tem){
                    index = j;
                    tem = arr[j];
                }
            }//找到最小的元素，然后和当前的元素交换
            swap(arr[i], arr[index]);
        }
    }

***4.快速排序***

快速排序思想：在数组中随机找一个数，然后遍历数组中的数，如果这个数大于所选的数则放在数组的前面，小于所选的数就放在数组的后面，然后在小于该数的部分和大于该数的部分继续进行上面的操作，直到数组只有一个数，这里利用了分治的思想。

快速排序是不稳定排序，时间复杂度为![o(nlogn\})][o_nlogn]，空间复杂度为![o(1)][o_1]

下面是代码：

void quicksort(vector<int> &arr, int left, int right){
        if(left >= right)
            return;
        int tem = arr[left];//以第一个元素作为判断，小于该数的放在前面，大于该数的放在后面
        int i = left;
        int j = right;
        while(i < j){
            while(i < j && arr[j] > tem){
                j--;
            }
            if(i < j){
                arr[i] = arr[j];
                i++;
            }
            while(i < j && arr[i] < tem){
                i++;
            }
            if(i < j){
                arr[j] = arr[i];
                j--;
            }
        }
        arr[i] = tem;
        quicksort(arr, left, i - 1);
        quicksort(arr, i + 1, right);
    }

***5.归并排序***

归并排序思想：将数组中的每个数作为一组，这样就会有N组，然后将N组两两合并，这样就变为![N/2][N_2]组，继续下去，知道最后变为一组。

归并排序是稳定排序，时间复杂度是![o(nlogn\})][o_nlogn]，空间复杂度为![o(1)][o_1]。

代码为：

void merge(vector<int> &arr, int left, int right, int mid){
        vector<int> tem(arr);
        int i = left;
        int j = mid + 1;
        int k = left;
        while(i <= mid && j <= right){
            if(arr[i] < arr[j]){
                tem[k] = arr[i];
                i++;
            }
            else{
                tem[k] = arr[j];
                j++;
            }
            k++;
        }
        while(i <= mid){
            tem[k] = arr[i];
            k++;
            i++;
        }
        while(j <= right){
            tem[k] = arr[j];
            j++;
            k++;
        }
        k = left;
        while(k <= right){
            arr[k] = tem[k];
            k++;
        }
    }
    void mergesort(vector<int> &arr, int left, int right){
        if(left >= right)
            return;
        int mid = (left + right) / 2;
        mergesort(arr, left, mid);
        mergesort(arr, mid + 1, right);
        merge(arr, left, right, mid);
    }

***6.堆排序***

堆排序思想：堆排序是通过建立大顶堆或者小顶堆的方法将数组排序。

堆排序不是稳定排序，时间复杂度为![o(nlogn\})][o_nlogn]，空间复杂度为![o(1)][o_1]。

代码如下：

void adjust(vector<int> &arr, int i, int len){
        int tem = arr[i];
        for(int k = 2 * i + 1; k < len; k = 2 * k + 1){
            if(k + 1 < len && arr[k + 1] > arr[k]){
                k = k + 1;
            }
            if(k < len && arr[k] > tem){
                arr[i] = arr[k];
                i = k;
            }
            else{
                break;
            }
        }
        arr[i] = tem;
    }
    void heapsort(vector<int> &arr){
        size_t len = arr.size();
        for(int i = len / 2 - 1; i >= 0; i--){
            adjust(arr, i, len);
        }
        for(int i = len - 1; i > 0; i--){
            swap(arr[i], arr[0]);
            adjust(arr, 0, i);
        }
    }

***7.希尔排序***

希尔排序可以说是插入排序的改进，希尔排序是将数组分组，然后对每一组进行插入排序，不断地将每组的数目进行缩小，最后将元素分为N组，这样就能实现排序。

希尔排序是不稳定排序，时间复杂度是![o(n^\{\\frac\{3\}\{2\}\})][o_n_frac_3_2]，空间复杂度为![o(1)][o_1]

代码如下：

void hillsort(vector<int> &arr){
        size_t len = arr.size();
        for(int gap = len / 2; gap > 0; gap /= 2){
            for(int i = gap; i < len; i++){
                int j = i - gap;
                while(j >= 0){
                    if(arr[j] > arr[i]){
                        swap(arr[j + gap], arr[j]);
                    }
                    else{
                        break;
                    }
                    j -= gap;
                }
            }
        }
    }

下面是各个算法对随机的一万个数据进行排序所有的时间：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MzY2NjE1_size_16_color_FFFFFF_t_70][]

[o_n_2]: https://private.codecogs.com/gif.latex?o%28n%5E%7B2%7D%29
[o_1]: https://private.codecogs.com/gif.latex?o%281%29
[o_nlogn]: https://private.codecogs.com/gif.latex?o%28nlogn%7D%29
[N_2]: https://private.codecogs.com/gif.latex?N/2
[o_n_frac_3_2]: https://private.codecogs.com/gif.latex?o%28n%5E%7B%5Cfrac%7B3%7D%7B2%7D%7D%29
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MzY2NjE1_size_16_color_FFFFFF_t_70]: /images/20220112/a892f99df9214d79ada1096724fdf0b8.png