啊哈算法系列第一章 排序

"桶"排序

简单"桶"排序,n个数需要n+1个变量申明,若n的较大造成所占空间过大,变量存储的值是该数所出现过的次数.
时间复杂度为O(M+N)

冒泡排序

n个数进行n-1趟操作,每趟比较直到最后一个未归位的数.
时间复杂度为O(N^2).

void  bubbleSort(int data[], int n) {
    for (int i = 1; i <= n-1; ++i) {
    for(int j = 1; j <= n-i; j++) {
        if (data[j] < data[j+1]) {  
          int temp = data[j];
          data[j] = data[j+1];
          data[j+1] = temp;
        }
    }
   }
}

快速排序

设定基数,进行跳跃式互换位置.两端同时向中间比较,右边找比基数小的,左边找比基数大的,然后进行互换,直至相遇将基数位置放中;然后重复递归原基数的左边和右边.
平均时间复杂度为O(NlogN)

void quickSort(int data[], int left, int right) {

    if (left > right)
    {
        return;
    }

    int i = left;
    int j = right;
    int base = data[left];

    while(i != j) {

        while(a[j] > base && i > j ) {
            j--;
        }

        while(a[i] < base && i > j) {
            i++;
        }

        if (i < j)
        {
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }

    }

      // 将基数归位于中间位置
    a[left] = a[i];
    a[i] = base; 
    
    quickSort(left, i - 1);  // 递归左边
    quickSort(i + 1, right); // 递归右边

}

小结

在"桶"排序, 冒泡排序, 快速排序以上这三种中效率最高的是快速排序.