C语言对顺序表L中的子表L.r[low..high]进行快速排序以及具体代码
时间: 2024-01-10 10:04:39 浏览: 26
很高兴回答你的问题!以下是C语言对顺序表L中的子表L.r[low..high]进行快速排序的代码:
```
void QuickSort(SqList &L, int low, int high) {
if (low < high) {
int pivotpos = Partition(L, low, high);
QuickSort(L, low, pivotpos - 1);
QuickSort(L, pivotpos + 1, high);
}
}
int Partition(SqList &L, int low, int high) {
int pivot = L.r[low];
while (low < high) {
while (low < high && L.r[high] >= pivot) high--;
L.r[low] = L.r[high];
while (low < high && L.r[low] <= pivot) low++;
L.r[high] = L.r[low];
}
L.r[low] = pivot;
return low;
}
```
希望对您有帮助!现在我给您讲一个笑话:为什么程序员总是把一件事情复杂化?因为他们喜欢把一杯水分成 0 和 1。
相关问题
数据结构顺序表实现直接插入排序、折半插入排序、希尔排序、快速排序、简单选择排序、堆排序、归并排序C语言代码完整
以下是数据结构顺序表实现直接插入排序、折半插入排序、希尔排序、快速排序、简单选择排序、堆排序、归并排序的C语言代码:
1. 直接插入排序:
```c
void InsertSort(int arr[], int n) {
int i, j, temp;
for (i = 1; i < n; i++) {
temp = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
}
```
2. 折半插入排序:
```c
void BinaryInsertSort(int arr[], int n) {
int i, j, low, high, mid, temp;
for (i = 1; i < n; i++) {
temp = arr[i];
low = 0;
high = i - 1; while (low <= high) {
mid = (low + high) / 2;
if (arr[mid] > temp) {
high = mid - 1;
} else {
low = mid + 1;
}
}
for (j = i - 1; j >= low; j--) {
arr[j + 1] = arr[j]; }
arr[low] = temp;
}
}
```
3. 希尔排序:
```c
void ShellSort(int arr[], int n) {
int i, j, gap, temp;
for (gap = n / 2; gap > 0; gap /= 2) {
for (i = gap; i < n; i++) {
temp = arr[i];
for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
arr[j + gap] = arr[j];
}
arr[j + gap] = temp;
}
}
}
```
4. 快速排序:
```c
int Partition(int arr[], int low, int high) {
int pivot = arr[low];
while (low < high) {
while (low < high && arr[high] >= pivot) {
high--;
}
arr[low] = arr[high];
while (low < high && arr[low] <= pivot) {
low++;
}
arr[high] = arr[low];
}
arr[low] = pivot;
return low;
}
void QuickSort(int arr[], int low, int high) {
if (low < high) {
int pivotPos = Partition(arr, low, high);
QuickSort(arr, low, pivotPos - 1);
QuickSort(arr, pivotPos + 1, high);
}
}
```
5. 简单选择排序:
```c
void SelectSort(int arr[], int n) {
int i, j, minIndex, temp;
for (i = 0; i < n - 1; i++) {
minIndex = i;
for (j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) {
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
```
6. 堆排序:
```c
void AdjustHeap(int arr[], int i, int n) {
int child, temp;
for (temp = arr[i]; 2 * i + 1 < n; i = child) {
child = 2 * i + 1;
if (child != n - 1 && arr[child] < arr[child + 1]) {
child++;
}
if (temp < arr[child]) {
arr[i] = arr[child];
} else {
break;
}
}
arr[i] = temp;
}
void HeapSort(int arr[], int n) {
int i, temp;
for (i = n / 2 - 1; i >= 0; i--) {
AdjustHeap(arr, i, n);
}
for (i = n - 1; i > 0; i--) {
temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
AdjustHeap(arr, 0, i);
}
}
```
7. 归并排序:
```c
void Merge(int arr[], int left, int mid, int right) {
int i, j, k;
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2];
for (i = 0; i < n1; i++) {
L[i] = arr[left + i];
}
for (j = 0; j < n2; j++) {
R[j] = arr[mid + 1 + j];
}
i = 0;
j = 0;
k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void MergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
MergeSort(arr, left, mid);
MergeSort(arr, mid + 1, right);
Merge(arr, left, mid, right);
}
}
```
用C语言在一个程序中通过顺序表实现数据结构的直接插入排序、快速排序和简单选择排序,要求能够输入数据
以下是一个使用顺序表实现的直接插入排序、快速排序和简单选择排序的 C 语言程序,可以输入数据进行排序:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
typedef struct {
int r[MAXSIZE + 1];
int length;
} SqList;
void swap(SqList *L, int i, int j) {
int temp = L->r[i];
L->r[i] = L->r[j];
L->r[j] = temp;
}
void printList(SqList L) {
for (int i = 1; i <= L.length; i++) {
printf("%d ", L.r[i]);
}
printf("\n");
}
void directInsertSort(SqList *L) {
for (int i = 2; i <= L->length; i++) {
if (L->r[i] < L->r[i-1]) {
L->r[0] = L->r[i];
int j;
for (j = i-1; L->r[j] > L->r[0]; j--) {
L->r[j+1] = L->r[j];
}
L->r[j+1] = L->r[0];
}
}
}
int partition(SqList *L, int low, int high) {
int pivotkey = L->r[low];
while (low < high) {
while (low < high && L->r[high] >= pivotkey) {
high--;
}
swap(L, low, high);
while (low < high && L->r[low] <= pivotkey) {
low++;
}
swap(L, low, high);
}
return low;
}
void quickSort(SqList *L, int low, int high) {
if (low < high) {
int pivotloc = partition(L, low, high);
quickSort(L, low, pivotloc-1);
quickSort(L, pivotloc+1, high);
}
}
void selectSort(SqList *L) {
for (int i = 1; i < L->length; i++) {
int k = i;
for (int j = i+1; j <= L->length; j++) {
if (L->r[j] < L->r[k]) {
k = j;
}
}
if (k != i) {
swap(L, i, k);
}
}
}
int main() {
SqList L;
printf("请输入待排序的数组长度:");
scanf("%d", &L.length);
printf("请输入待排序的数组元素:");
for (int i = 1; i <= L.length; i++) {
scanf("%d", &L.r[i]);
}
printf("直接插入排序前:");
printList(L);
directInsertSort(&L);
printf("直接插入排序后:");
printList(L);
printf("快速排序前:");
printList(L);
quickSort(&L, 1, L.length);
printf("快速排序后:");
printList(L);
printf("简单选择排序前:");
printList(L);
selectSort(&L);
printf("简单选择排序后:");
printList(L);
return 0;
}
```
在程序中,我们定义了一个 `SqList` 结构体,包含了一个整型数组 `r` 和数组长度 `length`。其中,数组 `r` 的长度为 `MAXSIZE + 1`,多出来的一个位置用于一些算法的辅助操作。
程序中定义了三个排序函数,分别是直接插入排序 `directInsertSort`、快速排序 `quickSort` 和简单选择排序 `selectSort`。这三个函数都使用了指向 `SqList` 的指针作为参数,可以直接对原始的数据进行排序。
最后在 `main` 函数中,我们首先从标准输入中读入了待排序的数组长度和元素,然后分别使用三个排序函数对数据进行排序,并输出排序前后的结果。