排序算法

时间复杂度O(n**2)

冒泡排序

排序思想：一边比较一边向后两两交换，将最大值 / 最小值冒泡到最后一位

/*
	thought for code:
		冒泡排序要交换n-1次,这是第一层循环
		在每一次交换中都会把最大的数放到最右边,此时最右边这个数便不用参加排序了
		因此，第二层循环的条件是-i
*/
int array[] = { 4, 3, 5, 1 }, temp = 0;
for (int i = 0; i < sizeof(array) / sizeof(array[0]) - 1; i++) {
    for (int j = 0; j < sizeof(array) / sizeof(array[0]) - 1 - i; j++) {
        if (array[j] > array[j + 1]) {
            temp = array[j + 1];
            array[j + 1] = array[j];
            array[j] = temp;
        }
    }
}

选择排序

选择排序：双重循环遍历数组，每经过一轮比较，找到最小元素的下标，将其交换至首位

/*
	thought for code:
		选择排序从前向后依次遍历，找到每个下标对应的最小元素值
		第一层循环是各自找出每个下标的位置
		第二层循环是找出对应下标的最小元素值
		因为其前面肯定是比她小,以只用考虑后面即可
		找到其后面的最小值的下标，交换即可
*/
for (int i = 0; i < 3; i++) {
    int minValIndex = i;
    for (int j = i + 1; j < 4; j++) {
        if (array[minValIndex] > array[j]) {
            minValIndex = j;
        }
    }
    temp = array[i];
    array[i] = array[minValIndex];
    array[minValIndex] = temp;
}

冒泡排序法是稳定的，选择排序法是不稳定的
什么是稳定？假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变。
冒泡排序中，只有左边的数字大于右边的数字时才会发生交换，相等的数字之间不会发生交换，所以它是稳定的。
而选择排序中，最小值和首位交换的过程可能会破坏稳定性。比如数列：[2, 2, 1]，在选择排序中第一次进行交换时，原数列中的两个 2 的相对顺序就被改变了，因此，我们说选择排序是不稳定的

插入排序

插入排序：在新数字插入过程中，与前面的数字不断比较，前面的数字不断向后挪出位置，当新数字找到自己的位置后，插入一次即可（移动法）

/*
	thought for code:
		依次遍历每个元素,和她前面的元素进行比较，如果小于前面的元素就把前面的元素后移
		直到她大于她前面的元素(j),此时就将这个位置(j + 1)赋值本元素
*/
for (int i = 1; i < 4; i++) {
    int currentVal = array[i];
    int j = i - 1;
    while (j >= 0 && currentVal < array[j]) {
        array[j + 1] = array[j];
        j--;
    }
    array[j + 1] = currentVal;
}

插入排序是一种稳定的排序算法

时间复杂度O(nlogn)

希尔排序

希尔排序是不稳定的

算了太拉了，不想讲解

堆排序

堆排序：

用数列构建出一个大顶堆，取出堆顶的数字；
调整剩余的数字，构建出新的大顶堆，再次取出堆顶的数字；
循环往复，完成整个排序。

根节点的值 ≥ 子节点的值，这样的堆被称之为最大堆，或大顶堆；
根节点的值 ≤ 子节点的值，这样的堆被称之为最小堆，或小顶堆；

快速排序

快速排序：

从数组中取出一个数，称之为基数（pivot）
遍历数组，将比基数大的数字放到它的右边，比基数小的数字放到它的左边。遍历完成后，数组被分成了左右两个区域
将左右两个区域视为两个数组，重复前两个步骤，直到排序完成

void quickSort(int* array, int start, int end) {
    if (start >= end) {
        return;
    }
    int middle = partition(array, start, end);
    quickSort(array, start, middle - 1);
    quickSort(array, middle + 1, end);
}
int partition(int* array, int start, int end) {
    int pivot = array[start];
    int left = start + 1;
    int right = end;
    while (left < right) {
        while (left < right && array[left] < pivot) {
            left++;
        }
        if (left != right) {
            swap(array, left, right);
            right--;
        }
    }
    if (left == right && array[right] > pivot) {
        right--;
    }
    if (start != right) {
        swap(array, start, right);
    }
    return right;
}
void swap(int* array, int m, int n) {
    int temp = array[m];
    array[m] = array[n];
    array[n] = temp;
}