void sortArray(vector<int>& nums) {
	int length = nums.size();
	for (int i = 1; i < length; i++) {
		int record = nums[i];
		int j = i - 1;
		// 空出插入record的位置
		while (j >= 0 && nums[j] > record) {
			nums[j + 1] = nums[j];
			j--;
		}
		// 插入
		nums[j + 1] = record;
	}
}

void sortArray(vector<int>& nums) {
   int length = nums.size();

	    for (int delta = length/2; delta > 0; delta /= 2) {
            // 遍历每个相距为delta的序列
            for (int start = 0; start < delta; start++) {

                // 以相距为delta的序列应用插入排序
                for (int i = delta + start; i < length; i += delta) {
                    int record = nums[i];
                    int j = i - delta;
                    // 空出插入record的位置
                    while (j >= 0 && nums[j] > record) {
                        nums[j + delta] = nums[j];
                        j -= delta;
                    }
                    // 插入
                    nums[j + delta] = record;
                }

            }
	    }
}

void sortArray(vector<int>& nums) {
	int length = nums.size();
	for (int i = 0; i < length ; i++){

		// 找到i之后最小的值
		int minIndex = i;
		int minValue = nums[i];
		for (int j = i; j < length ; j++){
			if(minValue>nums[j]){
				minIndex = j;
				minValue = nums[j];
			}
		}
		// 交换
		swap(nums[i], nums[minIndex]);
	}
}

void sortArray(vector<int>& nums) {
	int length = nums.size();
	priority_queue<int> max_heap;

	// 建堆
	for (int i = 0; i < length; i++) {
		max_heap.push(nums[i]);
	}

	for (int i = length - 1; i >= 0; i--) {
		nums[i] = max_heap.top();
		max_heap.pop();
	}
}

void sortArray(vector<int>& nums) {
	int length = nums.size();
	for (int i = 0; i < length - 1; i++) {
		bool isSwap = false;

		// 冒泡
		for (int j = length - 1; j > i; j--) {
			if (nums[j] < nums[j - 1]) {
				// 交换
				swap(nums[j], nums[j - 1]);
				isSwap = true;
			}
		}
		// 未发生交换说明已经全部排序完成
		if (!isSwap) {
			return;
		}
	}
}

void QuickSort(vector<int>& nums, int left, int right) {

	if (left >= right) {
		return;
	}

	// 选择轴值
	int pivot = (right - left) / 2 + left;
	int record = nums[pivot];

	// 每次从左边或右边拿出大于或小于pivot的值放到对面
	// 交替执行
	int l = left;
	int r = right;
	nums[pivot] = nums[right];
	while (l < r) {
		while (nums[l] <= record && l < r) {
			l++;
		}
		if (l < r) {
			nums[r--] = nums[l];
		}
		while (nums[r] > record && l < r) {
			r--;
		}
		if (l < r) {
			nums[l++] = nums[r];
		}
	}
	nums[l] = record;

	QuickSort(nums, left, l - 1);
	QuickSort(nums, l + 1, right);
}

void bucketSort(vector<int>& array, int min, int max) {
	int n = array.size();
	// 辅助数组长度
	int m = max - min + 1;
	vector<int> count(m, 0);
	vector<int> temp(n, 0);
	for (int i = 0; i < n; i++) {
		temp[i] = array[i];
	}
	// 统计每个元素的个数
	for (int i = 0; i < n; i++) {
		count[array[i] - min]++;
	}
	// 统计小于等于i的元素个数
	for (int i = 1; i < m; i++) {
		count[i] += count[i - 1];
	}
	// 从后向前，保证稳定性
	for (int i = n - 1; i >= 0; i--) {
		array[--count[temp[i] - min]] = temp[i];
	}
}

// d:位数 radix:基数 minR:位最小值 maxR:位最大值
void RadixtSort(vector<int>& array, int d, int radix, int minR, int maxR) {
	int n = array.size();
	// 辅助数组长度
	int r = maxR - minR + 1;
	vector<int> count(r, 0);
	vector<int> temp(n, 0);
	// 对每一位应用计数排序
	for (int i = 0; i <= d; i++) {
		for (int j = 0; j < r; j++) {
			count[j] = 0;
		}
		// 统计每个元素个数
		for (int j = 0; j < n; j++) {
			int k = array[j] / (int)pow(radix, i) % radix;
			count[k - minR]++;
		}
		// 统计小于等于i的元素个数
		for (int j = 1; j < r; j++) {
			count[j] += count[j - 1];
		}
		for (int j = 0; j < n; j++) {
			temp[j] = array[j];
		}
		// 从后向前，保证稳定性
		for (int j = n - 1; j >= 0; j--) {
			int k = temp[j] / (int)pow(radix, i) % radix;
			array[--count[k - minR]] = temp[j];
		}
	}
}

void merge(vector<int>& array, vector<int>& temp, int left, int right, int middle) {
    if (left >= right) {
		return;
	}

	// 左序列正序，右序列倒序
	for (int i = left; i <= middle; i++) {
		temp[i] = array[i];
	}
	for (int i = middle + 1; i <= right; i++) {
		temp[right - (i - middle) + 1] = array[i];
	}

	// 左右子序列索引
	int index1 = left;
	int index2 = right;
	// 合并后的索引
	int index = left;
	// 从左右序列两边向中间的方向，归并
	while (index <= right) {
		if (temp[index1] <= temp[index2]) {
			array[index++] = temp[index1++];
		} else {
			array[index++] = temp[index2--];
		}
	}
}
void MergeSort(vector<int>& array, vector<int>& temp, int left, int right) {
	if (left >= right) {
		return;
	}
	int middle = (right - left) / 2 + left;

	MergeSort(array, temp, left, middle);
	MergeSort(array, temp, middle + 1, right);
	merge(array, temp, left, right, middle);
}