许吉友 - 运维

排序算法

冒泡排序

#include <stdio.h>

#define length 10

/*
 *冒泡排序,时间复杂度为n的2次方
 * */

void maopao_sort(int arr[], int n){
        for (int i = 0; i < n; i++){
                for (int j = n-1; j > i; j--){
                        if (arr[j] > arr[j-1]){
                            int temp = arr[j];
                            arr[j] = arr[j-1];
                            arr[j-1] = temp;    
                        }
                }
        }
}

//高效版本,如果上次没有得到转换,则不进行下次的排序
void maopao_sort2(int arr[],int n){
        int flag;
        for (int i = 0; i < n-1; i++){
                flag = 0;
                for (int j = n-1; j > i; j--){
                        if (arr[j] > arr[j-1]){
                            int temp = arr[j];
                            arr[j] = arr[j-1];
                            arr[j-1] = temp;    
                            flag = 1;
                        }
                }
                if (flag == 0){
                        printf("跳出位置:%d\n",i);
                        break;
                }
        }

}

int main(){
        int arr[length] = {5,4,3,2,6,1,7,8,9,10};
        printf("按照从大到小排序,未排序前:\n");
        for(int i = 0; i < length; i++){
                printf(" %d ",arr[i]);
        }
        printf("\n");
        maopao_sort2(arr,length);
        printf("冒泡排序后\n");
        for(int i = 0; i < length; i++){
                printf(" %d ",arr[i]);
        }
        printf("\n");
        return 0;
}

快排序

#include <stdio.h>

#define length 10

/*
 *快排序,使用的归并法。
 快速排序稳定性
 快速排序是不稳定的算法,它不满足稳定算法的定义。
 算法稳定性 -- 假设在数列中存在a[i]=a[j],若在排序之前,a[i]在a[j]前面;并且排序之后,a[i]仍然在a[j]前面。则这个排序算法是稳定的!
 快速排序时间复杂度
 快速排序的时间复杂度在最坏情况下是O(N2),平均的时间复杂度是O(N*lgN)。
 这句话很好理解:假设被排序的数列中有N个数。遍历一次的时间复杂度是O(N),需要遍历多少次呢?至少lg(N+1)次,最多N次。
 (01) 为什么最少是lg(N+1)次?快速排序是采用的分治法进行遍历的,我们将它看作一棵二叉树,它需要遍历的次数就是二叉树的深度,而根据完全二叉树的定义,它的深度至少是lg(N+1)。因此,快速排序的遍历次数最少是lg(N+1)次。
 (02) 为什么最多是N次?这个应该非常简单,还是将快速排序看作一棵二叉树,它的深度最大是N。因此,快读排序的遍历次数最多是N次。
 * */

void kuai_sort(int arr[],int l, int r){
        if (l < r){
                int i = l;
                int j = r;
                int x = arr[l];
                while(i < j){
                        while(i < j && arr[j] < x){ //arr[j] < x用于从大到小排序, > 是从小到大,下个while倒过来
                                j--;
                        }        
                        if (i < j){
                                arr[i] = arr[j];
                                i++;
                        }
                        while(i < j && arr[i] > x){
                                i++;
                        }
                        if (i < j){
                                arr[j] = arr[i];
                                j--;
                        }
                }
                arr[i] = x;
                kuai_sort(arr, l,i-1);
                kuai_sort(arr, i+1, r);
        }
}

int main(){
        int arr[length] = {0,1,2,3,4,5,6,7,8,9};
        kuai_sort(arr, 0, length-1);
        for(int i = 0; i < length; i++){
                printf(" %d ",arr[i]);
        }
        printf("\n");
}

归并排序

#include <stdio.h>
#include <stdlib.h>

#define length 10

void guibing(int arr[], int start, int end, int mid){
        int *temp = (int *)malloc((end-start+1)*sizeof(int));
        int i = start;        //数组上半部分的下标
        int j = mid + 1;    //数组下半部分的下标
        int k = 0;            //temp的下标
        while(i <= mid && j <= end){
                if (arr[i] < arr[j]){
                        temp[k++] = arr[j++];
                } else {
                        temp[k++] = arr[i++];
                }
        }
        while(i <= mid){
                temp[k++] = arr[i++];
        }
        while(j <= end){
                temp[k++] = arr[j++];
        }
        for (int i = 0; i < k; i++){
                arr[start+i] = temp[i];
        }
        free(temp);
}

void guibing_uptodown(int arr[], int start, int end){
        if (arr == NULL || end <= start){
                return;
        }
        int mid = (end+start)/2;
        guibing_uptodown(arr,start,mid);
        guibing_uptodown(arr,mid+1,end);
        guibing(arr,start,end,mid);
}

int main(){
        int arr[length] = {1,2,3,4,5,6,7,8,9,0};
        guibing_uptodown(arr,0,length-1);
        for(int i = 0; i < length; i++){
                printf(" %d ",arr[i]);
        }
        printf("\n");
}

总结

参考:https://labuladong.gitbook.io/algo/di-ling-zhang-bi-du-xi-lie/er-cha-shu-xi-lie-1

快速排序就是个二叉树的前序遍历,归并排序就是个二叉树的后续遍历。

快速排序的逻辑是,若要对 nums[lo..hi] 进行排序,我们先找一个分界点 p,通过交换元素使得 nums[lo..p-1] 都小于等于 nums[p],且 nums[p+1..hi] 都大于 nums[p],然后递归地去 nums[lo..p-1]nums[p+1..hi] 中寻找新的分界点,最后整个数组就被排序了。

再说说归并排序的逻辑,若要对 nums[lo..hi] 进行排序,我们先对 nums[lo..mid] 排序,再对 nums[mid+1..hi] 排序,最后把这两个有序的子数组合并,整个数组就排好序了。