算法-排序

最近将之前的算法知识进行梳理，总结了三种常见的排序算法。废话不多说，上图上代码，看解析

冒泡排序

原理：
1.临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换。
2.这样一趟过去后,最大或最小的数字被交换到了最后一位。
3.然后再从头开始进行两两比较交换,直到倒数第二位时结束。

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

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        
        int a[6] = {9,6,2,7,1,8};
        bubble_sort(a, 6);
        
    }
    return 0;
}

bubble_sort

快速排序

原理：
快速排序是对冒泡排序的一种改进，基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对两部分记录继续进行排序。

void quick_sort(int *a, int left, int right)
{
    if(left > right){
        return;
    }
    int i = left;
    int j = right;
    int key = a[left];
    while (i < j) {
        while (i < j && key <= a[j]) {
            j--;
        }
        a[i] = a[j];
        while (i < j && key >= a[i]) {
            i++;
        }
        a[j] = a[I];
    }
    a[i] = key;
    //两边分别递归
    quick_sort(a, left, i - 1);
    quick_sort(a, i + 1, right);
}

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        
        int a[6] = {6,2,7,3,8,9};
        //第二个参数：起始索引
        //第三个参数：结束索引
        quick_sort(a,0,5);

    }
    return 0;
}

创建变量i=0（指向第一个数据）, j=5(指向最后一个数据), k=6(赋值为第一个数据的值)。

quick_sort

选择排序

原理：
从所有序列中先找到最小的，然后放到第一个位置。之后再看剩余元素中最小的，放到第二个位置……以此类推，就可以完成整个的排序工作了。

void select_sort(int a[], int n)
{
    for (int i = 0; i < n; i++) {
        int temp = 0;
        int min = a[I];
        int index = I;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < min) {
                min = a[j];
                index = j;
            }
        }
        temp = a[I];
        a[i] = min;
        a[index] = temp;
    }
}

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        
        int a[6] = {9,6,2,7,1,8};
        select_sort(a,6);
        
    }
    return 0;
}

select_sort

总结

名称	时间复杂度	空间复杂度	是否稳定
冒泡排序	O(n^2)	O(1)	是
快速排序	O(nlogn)	O(logn)	否
选择排序	O(n^2)	O(1)	否

在实际应用中，根据需求选择合适的排序算法。
其他常用的排序算法还有：插入排序，堆排序，归并排序，桶排序。