编辑代码

#include <stdio.h>
#include "windows.h"

#define MaxVertex 6     // 规定矩阵最大可存多少个结点

#define INF 210000000
#define N 7

// 冒泡算法,优化版(yyq)
void bubbleSort(int matrix[], int n) {
    int x = 0;
    for (int i = 0; i < n - 1; ++i) {
        if (x == n - i) return;
        x = 0;
        for (int j = 1; j < n - i; ++j) {
            if (matrix[j - 1] > matrix[j]) {
                int tmp = matrix[j];
                matrix[j] = matrix[j - 1];
                matrix[j - 1] = tmp;
            } else x++;
        }
    }
}

// 冒泡算法,优化版(qhxg)
void bubbleSort1(int matrix[], int n) {
    for (int i = 0; i < n - 1; ++i) {
        int flag = 1;
        for (int j = 1; j < n - i; ++j) {
            if (matrix[j - 1] > matrix[j]) {
                flag = 0;
                int tmp = matrix[j];
                matrix[j] = matrix[j - 1];
                matrix[j - 1] = tmp;
            }
        }
        if (flag) return;
    }
}

// 插入算法,最基本(没优化版)
void insertSort(int arr[], int size) {
    for (int i = 1; i < size; ++i) {
        for (int j = i; j > 0; j--) {
            if (arr[j] < arr[j - 1]) {
                int tmp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = tmp;
            } else break;
        }
    }
}

// 插入算法,最基本(没优化版)
void insertSort1(int arr[], int size) {
    for (int i = 1; i < size; ++i) {
        int tmp = arr[i];
        for (int j = i; j > 0; j--) {
            if (tmp < arr[j - 1]) {
                arr[j] = arr[j - 1];
            } else {
                arr[j] = tmp;
                break;
            }
        }
    }
}

// 交换方法
void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

// 选择排序(优化版)
void selectSort(int arr[], int size) {
    int left = 0, right = size - 1;
    while (left < right) {
        int max = left;
        int min = right;
        for (int j = left; j <= right; ++j) {
            if (arr[min] > arr[j]) min = j;
            if (arr[max] < arr[j]) max = j;
        }
        swap(&arr[right], &arr[max]);
        // 判断 right是不是min,是的话要交换一下
        if (min == right) min = max;
        swap(&arr[left], &arr[min]);
        left++;
        right--;
    }
}

// 冒泡排序进阶-> 快速排序
void quickSort(int arr[], int start, int end) {
    if (start >= end) return;
    int left = start, right = end, pivot = arr[start];
    while (left >= right) {
        while (arr[right] > pivot && left < right) right--;
        arr[left] = arr[right];
        while (arr[left] < pivot && left < right) left++;
        arr[right] = arr[left];
    }
    arr[left] = pivot;
    quickSort(arr, start, left - 1);
    quickSort(arr, left + 1, end);
}

// 双链快速排序(快速排序升级^^^^) 适合大数组
void dualPivotQuickSort(int arr[], int start, int end) {
    if (start >= end) return;
    if (arr[start] > arr[end]) swap(&arr[start], &arr[end]);
    int pivot1 = arr[start], pivot2 = arr[end];
    int left = start, mid = start + 1, right = end;
    while (mid >= right) {
        if (arr[mid] < pivot1) {
            swap(&arr[++left], &arr[mid++]);
        } else if (arr[mid] <= pivot2) mid++;
        else {
            while (arr[right] > pivot2 && right > mid) right--;
            if (mid >= right) break;
            swap(&arr[mid], &arr[right]);
        }
    }
    swap(&pivot1, &arr[left]);
    swap(&pivot2, &arr[right]);
    dualPivotQuickSort(arr, start, left - 1);
    dualPivotQuickSort(arr, left + 1, mid - 1);
    dualPivotQuickSort(arr, mid - 1, end);
}

// 希尔排序(插入排序^^^^^ yyq) 时间复杂度高一点
void shellSort(int arr[], int size) {
    int delta = size / 2;
    while (delta >= 1) {
        // 插入排序外面套个分组
        for (int i = delta; i < size; ++i) {    // 从delta开始,以步长delta为一组
            int tmp = arr[i];
            for (int j = i; j > 0; j -= delta) {    // 按照delta为步长开始排序
                if (tmp < arr[j - delta]) {
                    arr[j] = arr[j - delta];
                } else {
                    arr[j] = tmp;
                    break;
                }
            }
        }
        delta /= 2;
    }
}

// 希尔排序(qhxg)
void shellSort1(int arr[], int size) {
    int delta = size / 2;
    while (delta >= 1) {
        for (int i = delta; i < size; ++i) {
            int j = i, tmp = arr[i];
            while (j >= delta && arr[j - delta] > tmp) {
                arr[j] = arr[j - delta];
                j -= delta;
            }
            arr[j] = tmp;
        }
        delta /= 2;     // 计算步长分组
    }
}

// 堆排序 堆化(yyq)
void makeHeap(int *arr, int start, int end) {
    int flag = 1;
    int paren = end / 2;
    while (paren >= 0) {

        if (arr[paren * 2 + 1] && arr[paren * 2 + 1] > arr[paren]) {
            flag = 0;
            swap(&arr[paren], &arr[paren * 2 + 1]);
        } else if (arr[paren] < arr[paren * 2]) {
            swap(&arr[paren], &arr[paren * 2]);
            flag = 0;
        }

        paren--;
    }
    if (flag) return;
    makeHeap(arr, start, end);
}

// 堆排序(yyq)
void heapSort(int arr[], int size) {
    while (size >= 2) {
        swap(&arr[0], &arr[size - 1]);
        makeHeap(arr, 0, --size);
    }
}

// 堆排序(qhsg)
//这个函数就是对start顶点位置的子树进行堆化
void makeHeap1(int* arr, int start, int end) {
    while (start * 2 + 1 <= end) {    //如果有子树,就一直往下,因为调整之后有可能子树又不满足性质了
        int child = start * 2 + 1;    //因为下标是从0开始,所以左孩子下标就是i * 2 + 1,右孩子下标就是i * 2 + 2
        if(child + 1 <= end && arr[child] < arr[child + 1])   //如果存在右孩子且右孩子比左孩子大
            child++;    //那就直接看右孩子
        if(arr[child] > arr[start])   //如果上面选出来的孩子,比父结点大,那么就需要交换,大的换上去,小的换下来
            swap(&arr[child], &arr[start]);
        start = child;   //继续按照同样的方式前往孩子结点进行调整
    }
}

void heapSort1(int arr[], int size) {
    for(int i= size/2 - 1; i >= 0; i--)   //我们首选需要对所有非叶子结点进行一次堆化操作,需要从最后一个到第一个,这里size/2计算的位置刚好是最后一个非叶子结点
        makeHeap(arr, i, size - 1);
    for (int i = size - 1; i > 0; i--) {   //接着我们需要一个一个把堆顶元素搬到后面,有序排列
        swap(&arr[i], &arr[0]);    //搬运实际上就是直接跟倒数第i个元素交换,这样,每次都能从堆顶取一个最大的过来
        makeHeap(arr, 0, i - 1);   //每次搬运完成后,因为堆底元素被换到堆顶了,所以需要再次对根结点重新进行堆化
    }
}


int main() {
    int matrix[N] = {4, 2, 7, 1, 5, 3, 6};

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j)
            printf("%d ", matrix[i]);
        putchar('\n');
    }
}