数据结构动态顺序表的九大排序算法c语言

以下是针对动态顺序表的九大排序算法的C语言代码实现：

1. 冒泡排序

void bubbleSort(DynamicList *list) {
    int i, j;
    for (i = 0; i < list->length - 1; i++) {
        for (j = 0; j < list->length - i - 1; j++) {
            if (list->data[j] > list->data[j + 1]) {
                int temp = list->data[j];
                list->data[j] = list->data[j + 1];
                list->data[j + 1] = temp;
            }
        }
    }
}

2. 选择排序

void selectionSort(DynamicList *list) {
    int i, j, minIndex;
    for (i = 0; i < list->length - 1; i++) {
        minIndex = i;
        for (j = i + 1; j < list->length; j++) {
            if (list->data[j] < list->data[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            int temp = list->data[i];
            list->data[i] = list->data[minIndex];
            list->data[minIndex] = temp;
        }
    }
}

3. 插入排序

void insertionSort(DynamicList *list) {
    int i, j, temp;
    for (i = 1; i < list->length; i++) {
        temp = list->data[i];
        for (j = i - 1; j >= 0 && list->data[j] > temp; j--) {
            list->data[j + 1] = list->data[j];
        }
        list->data[j + 1] = temp;
    }
}

4. 希尔排序

void shellSort(DynamicList *list) {
    int i, j, gap, temp;
    for (gap = list->length / 2; gap > 0; gap /= 2) {
        for (i = gap; i < list->length; i++) {
            temp = list->data[i];
            for (j = i - gap; j >= 0 && list->data[j] > temp; j -= gap) {
                list->data[j + gap] = list->data[j];
            }
            list->data[j + gap] = temp;
        }
    }
}

5. 快速排序

int partition(DynamicList *list, int low, int high) {
    int pivot = list->data[low];
    while (low < high) {
        while (low < high && list->data[high] >= pivot) {
            high--;
        }
        list->data[low] = list->data[high];
        while (low < high && list->data[low] <= pivot) {
            low++;
        }
        list->data[high] = list->data[low];
    }
    list->data[low] = pivot;
    return low;
}

void quickSort(DynamicList *list, int low, int high) {
    if (low < high) {
        int pivotPos = partition(list, low, high);
        quickSort(list, low, pivotPos - 1);
        quickSort(list, pivotPos + 1, high);
    }
}

6. 归并排序

void merge(DynamicList *list, 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] = list->data[left + i];
    }
    for (j = 0; j < n2; j++) {
        R[j] = list->data[mid + j + 1];
    }
    i = j = 0;
    k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            list->data[k++] = L[i++];
        } else {
            list->data[k++] = R[j++];
        }
    }
    while (i < n1) {
        list->data[k++] = L[i++];
    }
    while (j < n2) {
        list->data[k++] = R[j++];
    }
}

void mergeSort(DynamicList *list, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(list, left, mid);
        mergeSort(list, mid + 1, right);
        merge(list, left, mid, right);
    }
}

7. 堆排序

void adjustHeap(DynamicList *list, int i, int len) {
    int temp = list->data[i];
    int j;
    for (j = 2 * i + 1; j < len; j = 2 * j + 1) {
        if (j + 1 < len && list->data[j] < list->data[j + 1]) {
            j++;
        }
        if (temp >= list->data[j]) {
            break;
        }
        list->data[i] = list->data[j];
        i = j;
    }
    list->data[i] = temp;
}

void heapSort(DynamicList *list) {
    int i;
    for (i = list->length / 2 - 1; i >= 0; i--) {
        adjustHeap(list, i, list->length);
    }
    for (i = list->length - 1; i > 0; i--) {
        int temp = list->data[0];
        list->data[0] = list->data[i];
        list->data[i] = temp;
        adjustHeap(list, 0, i);
    }
}

8. 计数排序

void countingSort(DynamicList *list) {
    int max = list->data[0], min = list->data[0], i, j;
    for (i = 1; i < list->length; i++) {
        if (list->data[i] > max) {
            max = list->data[i];
        }
        if (list->data[i] < min) {
            min = list->data[i];
        }
    }
    int count[max - min + 1];
    memset(count, 0, sizeof(count));
    for (i = 0; i < list->length; i++) {
        count[list->data[i] - min]++;
    }
    j = 0;
    for (i = 0; i < max - min + 1; i++) {
        while (count[i] > 0) {
            list->data[j++] = i + min;
            count[i]--;
        }
    }
}

9. 桶排序

void bucketSort(DynamicList *list) {
    int max = list->data[0], min = list->data[0], i, j;
    for (i = 1; i < list->length; i++) {
        if (list->data[i] > max) {
            max = list->data[i];
        }
        if (list->data[i] < min) {
            min = list->data[i];
        }
    }
    int bucketSize = 5;
    int bucketCount = (max - min) / bucketSize + 1;
    DynamicList *buckets[bucketCount];
    for (i = 0; i < bucketCount; i++) {
        buckets[i] = createList(bucketSize);
    }
    for (i = 0; i < list->length; i++) {
        int bucketIndex = (list->data[i] - min) / bucketSize;
        if (buckets[bucketIndex]->length == buckets[bucketIndex]->capacity) {
            expandList(buckets[bucketIndex]);
        }
        appendList(buckets[bucketIndex], list->data[i]);
    }
    j = 0;
    for (i = 0; i < bucketCount; i++) {
        if (buckets[i]->length > 0) {
            insertionSort(buckets[i]);
            memcpy(&list->data[j], buckets[i]->data, sizeof(int) * buckets[i]->length);
            j += buckets[i]->length;
            destroyList(buckets[i]);
        }
    }
}