void bubbleSort(std::vector<int>& nums) {
	for (int i = 0; i < nums.size(); i++) {
        for (int j = 0; j < nums.size() - i - 1; j++) {
            if (nums[j] > nums[j+1]) {
				std::swap(nums[j], nums[j+1]);
            }
        }
    }
}

void bubbleSort(std::vector<int>& nums) {
	for (int i = 0; i < nums.size(); i++) {
        int isExchange = 0;				// 用于记录本趟冒泡是否发生数据交换
        for (int j = 0; j < nums.size() - i - 1; j++) {
            if (nums[j] > nums[j+1]) {
				std::swap(nums[j], nums[j+1]);
                isExchange = 1;			// 发生数据交换, 置1
            }
        }
        // 一趟冒泡结束
        if (!isExchange) 
            break;				// 如果一趟冒泡结束了, 还没有发生数据交换
        						// 说明整个数组已经有序了, 可以退出外部循环
    }
}

void selectSort(std::vector<int>& nums) {
	for (int i = 0; i < nums.size(); i++) {
        int maxi = 0;
        int left =  nums.size() - i;		// left 是每趟需要放最大值的位置
        for (int j = 0; j <= left; j++) {
			if (nums[j] > nums[maxi]) {
				maxi = j;					// 记录最大值的坐标
            }
        }
        std::swap(nums[maxi], nums[left]);
    }
}

void selectSort(std::vector<int>& nums) {
    int left = 0;
    int right = nums.size() - 1;
    
    // 循环停止的条件就是两指针相遇
    while(left < right) {
        int mini = left;
        int maxi = left;
        for (int i = left; i <= right; i++) {
            if (nums[i] > nums[maxi])
                maxi = i;				// 记录最大值的位置
            if (nums[i] < nums[mini])
                mini = i;				// 记录最小值的位置
        }
        
        // 找完极值, 就可以交换数据
        std::swap(nums[maxi], nums[right]);
        // 将最大值放入有效范围的末尾之后
        // 不能再直接放最小值
        // 因为 mini 原本可能就在有效范围的末尾, 即right
        // 如果是这样, 原来的nums[mini]就被交换走了
        // 此时, nums[mini]其实就是刚放入的 nums[maxi]
        // 所以, 要先判断一下 mini 是否 就是right
        if (mini == right) {
            mini = maxi;
        }
        std::swap(nums[mini], nums[left]);
 
        // 缩小有效范围
        left++;
        right--;
    }
}

void insertSort(std::vector<int>& nums) {
    for (int i = 0; i < nums.size() - 1; i++) {
        int end = i;				// end 与 i同步
        int cur = nums[end+1];		// 记录nums[end+1], 因为前面的数据可能要往后移动, 会覆盖掉nums[end+1], 所以需要使用变量存储nums[end+1]
        int now = end;				// 从 end位置开始, 向前遍历对比数据大小
        
        // 当遍历到整个数组头结束
        while (now >= 0) {
			if (nums[now] > cur) {	// 对比数据比cur大, 数据向后移动一位
                nums[now+1] = nums[now];
                now--;
            }
            else {
				break; 				// 对比数据<=cur, 就表示找到了合适的位置
            }
        }
        
        // nums[now] <= cur, 就表示now+1位置为合适的位置
        nums[now+1] = cur;
        // 一趟排序结束
    }
}

void insertSort(std::vector<int>& nums) {
    for (int i = 0; i < nums.size() - 1; i++) {
        int end = i;				// end 与 i同步
        int cur = nums[end+1];		// 记录nums[end+1], 因为前面的数据可能要往后移动, 会覆盖掉nums[end+1], 所以需要使用变量存储nums[end+1]
        
        // 当遍历到整个数组头结束
        while (end >= 0) {
			if (nums[end] > cur) {	// 对比数据比cur大, 数据向后移动一位
                nums[end+1] = nums[end];
                now--;
            }
            else {
				break; 				// 对比数据<=cur, 就表示找到了合适的位置
            }
        }
        
        // nums[end] <= cur, 就表示end+1位置为合适的位置
        nums[end+1] = cur;
        // 一趟排序结束
    }
}

void shellSort(std::vector<int>& nums) {
    int gap = nums.size();

    while (gap > 1) {               // gap > 1 就继续预排序
        gap = gap / 3 + 1;          // 预排序 gap的取值方法
        for (int i = 0; i < gap; i++) {     // 外层循环次数 其实就是分出来的的组数
            for (int j = i; j < nums.size() - gap; j += gap) {
                int end = j;				// 对以gap为间隔分组的数据, 进行插入排序
                int cur = nums[end + gap];
                while (end >= 0) {
                    if (cur < nums[end]) {
                        nums[end + gap] = nums[end];
                        end -= gap;
                    }
                    else {
                        break;
                    }
                }
                nums[end + gap] = cur;
            }
        }
    }
}

void shellSort(std::vector<int>& nums) {
	int gap = nums.size();
    
    while (gap > 1) {
        gap = gap / 3 + 1;
        for (int i = 0; i < nums.size() - gap; i++) {
			int end = i;
            int cur = nums[end + gap];
            while (end >= 0) {
                if (cur < nums[end]) {
					nums[end + gap] = nums[end];
                    end -= gap;
                }
                else {
                    break;
                }
            }
            nums[end + gap] = cur;
        }
	}
}