第六章 排序
6.1冒泡排序
void swap(int arr[], int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
//外层循环是说明n个元素排好序需要经过n-1轮
for (int i = n - 1; i > 0; i--) {
bool flag = true;
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
flag = false;
swap(arr, j, j + 1);
}
}
if (flag == true) {
break;
}
}
/*for (int i = 0; i < n - 1; i++) {
for (int j = n - 1; j > i; j--) {
if (arr[j] > arr[j - 1]) {
swap(arr, j, j - 1);
}
}
}*/
//递归写法
void bubbleSort2(int arr[], int n) {
if (n == 1) {
return;
}
for (int i = 0; i < n-1; i++) {
if (arr[i] > arr[i + 1]) {
swap(arr, i, i + 1);
}
}
bubbleSort2(arr, --n);
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
6.2选择排序
//简单选择排序
void selectSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int min = arr[i];
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < min) {
min = arr[j];
minIndex = j;
}
}
if (minIndex != i) {
swap(arr, i, minIndex);
}
}
}
6.3直接插入排序
//插入排序
void insertSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j > 0 && arr[j] > arr[j - 1]; j--) {
swap(arr, j, j - 1);
}
}
}
6.4折半插入排序
int insertIndex(int arr[],int target, int n) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] <= target) {
low = mid + 1;
}
else {
high = mid - 1;
}
}
return low;
}
//折半插入排序
void binaryInsertSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int index = insertIndex(arr, arr[i], i);
for (int j = i; j > index; j--) {
swap(arr, j, j - 1);
}
}
}
6.5希尔排序
//希尔排序
void shellSort(int arr[], int n) {
for (int gap = n / 2; gap >= 1; gap /= 2) {
for (int i = gap; i < n; i++) {
for (int j = i; j >= gap && arr[j] < arr[j - gap]; j -= gap) {
swap(arr, j, j - gap);
}
}
}
}
//希尔排序
void shellSort(int arr[], int n) {
for (int gap = n / 2; gap >= 1; gap /= 2) {
for (int i = 0; i < n - gap; i++) {
for (int j = i + gap; j >= gap && arr[j] < arr[j - gap]; j -= gap) {
swap(arr, j, j - gap);
}
}
}
}
6.6快速排序
6.6.1双边快排，以第一个元素为枢轴元素
void swap(int arr[], int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
int partition(int arr[], int L, int R) {
int p = arr[L];
int i = L;
int j = R;
while (i < j) {
while (i < j && arr[j] >= p) {
j--;
}
while (i< j&& arr[i] <= p) {
i++;
}
swap(arr, i, j);
}
swap(arr, L, i);
return i;
}
void quick(int arr[], int L, int R) {
if (L >= R) {
return;
}
int pos = partition(arr, L, R);
quick(arr, L, pos - 1);
quick(arr, pos+1, R);
}
void quickSort(int arr[], int n) {
if (n < 2) {
return;
}
quick(arr, 0, n - 1);
}
6.6.2双边快排，以最后一个元素为枢轴元素
void swap(int arr[], int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
//双边快排（以最后一个元素为枢轴）
int partition3(int arr[], int L, int R) {
int p = arr[R];
int i = L;
int j = R;
while (i < j) {
while (i < j && arr[i] <= p) {
i++;
}
while (i < j && arr[j] >= p) {
j--;
}
swap(arr, i, j);
}
swap(arr, R, i);
return i;
}
void quick3(int arr[], int L, int R) {
if (L >= R) {
return;
}
int pos = partition3(arr, L, R);
quick3(arr, L, pos - 1);
quick3(arr, pos + 1, R);
}
void quickSort3(int arr[], int n) {
if (n < 2) {
return;
}
quick3(arr, 0, n - 1);
}
6.6.3双边快排，随机生成种子
//双边快排（以最后一个元素为枢轴）
void swap(int arr[], int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 生成随机索引
int randomIndex(int L, int R) {
return rand() % (R - L + 1) + L;
}
int partition4(int arr[], int L, int R) {
int randIdx = randomIndex(L, R);
int p = arr[randIdx];
// 将随机选择的元素移动到最后一个位置
int temp = arr[randIdx];
arr[randIdx] = arr[L];
arr[L] = temp;
int i = L;
int j = R;
while (i < j) {
while (i < j && arr[j] >= p) {
j--;
}
while (i < j && arr[i] <= p) {
i++;
}
swap(arr, i, j);
}
swap(arr, L, i);
return i;
}
void quick4(int arr[], int L, int R) {
if (L >= R) {
return;
}
int pos = partition4(arr, L, R);
quick4(arr, L, pos - 1);
quick4(arr, pos + 1, R);
}
void quickSort4(int arr[], int n) {
if (n < 2) {
return;
}
srand(time(NULL)); // 设置随机种子
quick4(arr, 0, n - 1);
}
6.7归并排序
int* newarr = NULL;
void merge(int arr[], int left, int mid, int right) {
for (int i = left; i <= right; i++) {
newarr[i] = arr[i];
}
int i = left;
int j = mid + 1;
int k = left;
while (i <= mid && j <= right) {
if (newarr[i] <= newarr[j]) {
arr[k++] = newarr[i++];
}
else {
arr[k++] = newarr[j++];
}
}
while (i <= mid) {
arr[k++] = newarr[i++];
}
while (j <= right) {
arr[k++] = newarr[j++];
}
}
void sort(int arr[], int left, int right) {
if (left >= right) {
return;
}
int mid = (left + right) / 2;
sort(arr, left, mid);
sort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
//归并排序(函数入口)
void mergeSort(int arr[], int n) {
if (n < 2) {
return;
}
newarr = (int*)malloc(sizeof(int) * n);
sort(arr, 0, n - 1);
}
6.8堆排序
//从下标为k的元素开始下潜
void down(int arr[], int k, int n) {
int left = k * 2 + 1;
int right = left + 1;
int max = k;
if (left < n && arr[left] > arr[max]) {
max = left;
}
if (right < n && arr[right] > arr[max]) {
max = right;
}
if (max != k) {
swap(arr,max, k);
down(arr,max,n);
}
}
//建堆
void heapify(int arr[], int n) {
for (int i = n / 2; i >= 0; i--) {
down(arr, i, n);
}
}
//堆排序
void heapSort(int arr[], int n) {
heapify(arr, n);
for (int i = n-1; i > 0; i--) {
swap(arr, i, 0);
down(arr, 0, i);
}
}
6.9刷题
1.以arr数组中第ki的元素作为分隔，使左边的元素值都比ki所对应的元素值小，右侧都比其大。
void change(int arr[], int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
//以arr数组中第ki的元素作为分隔，
//使左边的元素值都比ki所对应的元素值小，右侧都比其大
void quickPart(int arr[], int Ki, int n) {
//第ki个，所以先对ki合法性做个判断
if (Ki < 1 || Ki > n) {
return;
}
change(arr, 0, Ki - 1); //先将第ki个元素第一个交换，后面代码就可以直接用讲的了
int p = arr[0];
int i = 0;
int j = n - 1;
while (i < j) {
while (i < j && arr[j] >= p) {
j--;
}
while (i < j && arr[i] <= p) {
i++;
}
change(arr, i, j);
}
change(arr, 0, i);
}
1.已知线性表按顺序存储，且每个元素都是不相同的整数型元素，设计把所有奇数移动到
所有偶数前边的算法( 要求时间最短，辅助空间最小)。
void change(int arr[], int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
void oddFrontEvenLast(int arr[],int n) {
int low = 0, high = n - 1;
while (low < high) {
//找第一个偶数
while (low < high && arr[low] % 2 == 1) {
low++;
}
//找第一个奇数
while (low < high && arr[high] % 2 == 0) {
high--;
}
change(arr, low, high);
low++;
high--;
}
}
02.试编写一个算法，使之能够在数组L[1...n]中找出第k小的元素( 即从小到大排序后处
于第k个位置的元素)。
/*思路1：用小根堆找到K个，建立小根堆时间复杂度O(n)，k个下沉操作，时间复杂度O(klogn)，整体(n+klogn)*/
//从下标为k的元素开始下潜
void down(int arr[], int k, int n) {
int left = k * 2 + 1;
int right = left + 1;
int min = k;
if (left < n && arr[left] < arr[min]) {
min = left;
}
if (right < n && arr[right] < arr[min]) {
min = right;
}
if (min != k) {
change(arr, min, k);
down(arr, min, n);
}
}
//建小顶堆
void heapify(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--) {
down(arr, i, n);
}
}
/*
02.试编写一个算法，使之能够在数组L[1...n]中找出第k小的元素( 即从小到大排序后处
于第k个位置的元素)。
*/
int getKMin(int arr[], int k, int n) {
if (k < 1 || k > n) {
return -999; //出错
}
//先建立小顶堆
heapify(arr, n);
// 依次移除堆顶元素，直到第k小的元素
for (int i = 0; i < k - 1; i++) {
change(arr, 0, n - 1 - i);
down(arr, 0, n - i - 1);
}
// 第k小的元素即为当前堆顶元素
return arr[0];
}
/*思路2：利用快排思想，平均时间复杂度可达到O(n)*/
//L和R分别代表的是左右边界
int partition1(int arr[], int L, int R) {
int p = arr[L];
int i = L;
int j = R;
while (i < j) {
while (i < j && arr[j] >= p) {
j--;
}
while (i < j && arr[i] <= p) {
i++;
}
change(arr, i, j);
}
change(arr, L, i);
return i;
}
int quickPartition(int arr[], int k, int L,int R) {
int p = partition1(arr, L, R);
int rank = p - L + 1; // 计算当前划分后 pivot 的排名
if (rank == k) {
return arr[p]; // 找到第k小的元素
}
else if (k < rank) {
return quickPartition(arr, k, L, p - 1); // 在左侧继续查找
}
else {
return quickPartition(arr, k - rank, p + 1, R); // 在右侧继续查找
}
}
int getKMin2(int arr[], int k, int n) {
if (k < 1 || k > n) {
return -1;
}
return quickPartition(arr, k, 0, n - 1);
}
3.荷兰国旗问题:设有一个仅由红、白、蓝三种颜色的条块组成的条块序列，存储在
一个顺序表中，请编写一个时间复杂度为O(n)的算法，使得这些条块按红、白、蓝
的顺序排好，即排成荷兰国旗图案。请完成算法实现:
typedef enum { RED=0, WHITE=1, BLUE=2 } color;
void swap2(color a[], int i, int j) {
color temp = a[i];
a[i] = a[j];
a[j] = temp;
}
void Flag_Arrange(color a[], int n) {
int redPart = -1;
int bluePart = n;
int i = 0;
while (i < bluePart) {
if (a[i] == RED) {
swap2(a, i++, ++redPart);
}
else if (a[i] == BLUE) {
swap2(a, i, --bluePart);
}
else {
i++;
}
}
}
4.给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
示例 1：
输入：nums = [3,0,1] 输出：2 解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。示例 2：
输入：nums = [0,1] 输出：2 解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。示例 3：
输入：nums = [9,6,4,2,3,5,7,0,1] 输出：8 解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。示例 4：
输入：nums = [0] 输出：1 解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。
int missingNumber(int nums[], int n) {
int ans = 0;
for (int i = 0; i <= n; i++) {
if (i == n) {
ans ^= i;
}
else {
ans ^= (i ^ nums[i]);
}
}
return ans;
}
5.给定一个非负整数数组 nums， nums 中一半整数是 奇数 ，一半整数是 偶数 。对数组进行排序，以便当 nums[i] 为奇数时，i 也是 奇数 ；当 nums[i] 为偶数时， i 也是 偶数 。
示例 1：
输入：nums = [4,2,5,7] 输出：[4,5,2,7] 解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。示例 2：
输入：nums = [2,3] 输出：[2,3]
void change(int arr[], int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
void sortArrayByParityII(int nums[],int n) {
int high = n;
int low = 1;
for (int i = 0; i < high; i += 2) {
if ((nums[i] & 1) == 1) {
while (nums[low] % 2 == 1) {
low += 2;
}
change(nums, i, low);
}
}
}