内排序

冒泡排序

• 决定冒泡的方向，每次冒泡相邻元素比较，每次固定一个泡。
• 如果一趟未产生任何交换，则整个序列已排序，无需再比较。
• 时间复杂度：比较的次数n-1 … 1 , 总和 O(n^2) , 空间复杂度 O(1)

int a[100] = {1, 2, 10, 3, 5, 4, 2};
void swap(int i, int j) {
    if (i != j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}
//冒泡排序, 从小到大
void bubbleSort(int a[], int n) {
    if (n <= 1) {
        return;
    }

    for (int i = 0; i < n - 1; i++) { //每次要确定的冒泡元素
        int sorted = 1;  //做一个优化，如果一趟排序中都没有产生交换，则不需要以后操作
        for (int j = n - 1; j > i; j--) { //从后往前冒
            if (a[j] < a[j - 1]) {
                swap(j, j-1);
                sorted = 0;
            }
        }

        if (sorted == 1) {
            break;
        }
    }
}

快速排序

• 快排核心找基准数，把基准数放到某一个位置，左边的都比它小，右边的都比它大。
• 如果我们以最左边的为基准，那么需要注意的是为什么从右边找，因为从左边找，你可能无法找到比它小的元素，这样你就无法执行基准数和找到的数的交换，如果从右边找，至少可以找到刚好等于基准数的元素，这样才满足基准数左边都小于，右边都大于的思想。
• 时间复杂度：如果每次被二分，总共被分成的是logn 趟， 每次比较的是 n 次， 时间复杂度 O(nlogn), 空间复杂度 O(1) 。

void quickSortByRange(int a[], int left, int right){
    if (left >= right) {
        return;
    }
    int l = left;
    int r = right;
    int pivotIndex = left;
    int pivot = a[left];
    //基准数在左边，为什么是从右边找，而不是从左边找呢，因为如果从左边找，你很可能找不到，这样就无法执行
    //基准数和相遇点的交换了，而从左边找，至少可以直接找到基准数的这个位置
    while (left < right) {
        while (left < right && a[right] >= pivot) { //从右边找到比基准数小的那个
            right--;
        }
        while (left < right && a[left] <= pivot) {
            left++;
        }
        if (left < right) {
            swap(left, right);
        }
    }

    if (left <= right) { //在不出现越界的情况下，执行基准和相遇点的交换
        swap(pivotIndex, left);
        quickSortByRange(a, l, left - 1);
        quickSortByRange(a, left + 1, r);
    }
}
void quickSort(int a[], int n) {
    if (n <= 1) {
        return;
    }
    quickSortByRange(a, 0, n - 1);
}

插入排序

• 插入排序关键在于插入，分割为排序和未排序部分，不断把右边的元素插入到左边的序列中，注意是相邻元素交换。
• 时间复杂度：O(n^2), 空间复杂度 O(1)

void insertOrder(int array[], int n) {
    if (n <= 1) {
        return;
    }
    
     //每次选定一个元素同前面的已排序的元素做对比，找到应该插入的位置
    for (int i = 1; i < n; i++) {
        int key = array[i];
        
        int j = i - 1;
        while (j >= 0) {
            if (key > array[j]) {
                swap(array, j, j+1);
            }
            else {
                break;
            }
            j--;
        }
        
    }
}

选择排序

• 选择排序每次从未排序的队列中选择出最大或者最小元素，放到已排序的队列末尾。
• 时间复杂度: O(n^2) , 空间复杂度: O(1)

///选择排序,降序,
void selectOrder(int array[], int n) {
    if (n <= 1) {
        return;
    }

    //选择排序，每次从无序的被选的元素中找最大或者最小的放到有序的环境中
    for (int i = 0; i < n; i++){
        int selectIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (array[j] > array[i]) {
                selectIndex = j;
            }
        }
       swap(array, i, selectIndex);
    }
  }
}

其他

• 因为快排拥有比较好的平均时间复杂度，所以快排用的范围相对来说更广一些。