算法学习

1.冒泡
如果要让一个数组a[n]按照从小到大的顺序排序，可以让相邻的两个数比较大小，把较大的数排到后面，第一轮比较后，将数组里最大的数放到最后面，一共要比较n-1轮。

void bubble_sort(int a[], int n){//n为数组元素的个数
    for (int i = 0; i < n-1; i++) {
        int sortedComplete = 1;
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j]>a[j+1]) {
                sortedComplete = 0;
                int tem = 0;
                tem = a[j];
                a[j] = a[j + 1];
                a[j+1] = tem;
            }
        }
        if (sortedComplete) {//如果不是0，说明没有进行交换，也就是说顺序已经是正确的顺序,不需要再进行后面的排序了
            break;
        }
    }
}

int main(int argc, const char * argv[]) {
    bubble_sort(b, 10);
    for (int i = 0; i < 10; i++) {
        printf("%d\n", b[i]);
    }
    return 0;
}

从上面的代码可以看出，不考虑sortedComplete的话，时间复杂度是O(N*N)。
6 2 8 7

快排：

void quick_sort(int arr[], int start, int end){
    if (start >= end) {
        return;
    }
    
    int key = arr[start];
    int i = start;
    int j = end;
    
    while (i != j) {
        while (i<j && arr[j] >= key) {
            j--;
        }
        
        while (i<j && arr[i] <= key) {
            i++;
        }
        
        if (i!=j) {
            int tem = arr[i];
            arr[i] = arr[j];
            arr[j] = tem;
        }
    }
    
    arr[start] = arr[i];
    arr[i] = key;
    
    quick_sort(arr, start, i-1);
    quick_sort(arr, i+1, end);
}

从上面的代码可以看出，快排是先以数组的第一个数位基准数，从右边的下标high开始往前寻找，当找到小于基准数的下标时，在从左边的下标i开始寻找，找到大于基准数的下标,然后交换下标i和j对应的值，然后继续寻找，直到i=j时，此时交换基准数和j对应的数，保证了基准数左边的数都比基准数小，右边的数都比基准数要大。然后对基准数两边的自己递归地使用上面的方法，从而达到排序的效果。