typedef struct {
    int* data;
    int length;
} Sqlist;

void swap(Sqlist* L, int m, int n){
    int tem = L->data[m];
    L->data[m] = L->data[n];
    L->data[n] = tem;
}

void print(Sqlist L){
    int i = 1;
    for (i = 1; i < L.length; i++) {
        printf("%d", L.data[i]);
    }
    printf("%d",L.data[i]);
    printf("\n");
}

冒泡排序

//冒泡排序
void bubbleSort(Sqlist *L){
    int sorted = 1;//优化
    for (int i = 1; i < L->length; i++) {
        sorted = 0;
        for (int j = L->length-1; j > i; j--) {
            if (L->data[j] > L->data[j+1]) {
                swap(L, j, j+1);
                sorted = 1;
            }
        }
        if (sorted == 0) {//如果在对比的过程中发现已经有序，则不需要再进行对比
            break;
        }
    }
}

简单的选择排序

//简单的选择排序
void selectSort(Sqlist *L){
    int i, j , m;
    for (i = 1; i < L->length; i++) {
        m = i;//假设第一个最小
        for (j = i + 1; j <= L->length; j++) {
            if (L->data[m] > L->data[j]) {//那第一个和后面的比
                m = j;//直到找到最小
            }
        }
        if (i != m) {
            swap(L, i, m);//交换
        }
    }
}

插入排序

//插入排序
void insertSort(Sqlist *L){
    int i, j;
    int temp = 0;
    for (i = 2; i <= L->length; i++) {
        if (L->data[i] < L->data[i-1]) {
            temp = L->data[i];
            for (j = i - 1; L->data[j]>temp; j--) {
                    L->data[j+1] = L->data[j];
            }
            L->data[j + 1]=temp;
        }
       
    }
}

希尔排序

//希尔排序
void shellSort(Sqlist *L){
    int step = L->length;
    int tem = 0;
    int i,j;
    do {
        step = step/3 + 1;
        for (i = step + 1; i <= L->length; i++) {
            if (L->data[i] < L->data[i-step]) {
                tem = L->data[i];
                for (j = i - step; L->data[j]>tem; j-=step) {
                    L->data[j+step] = L->data[j];
                }
                j+=step;
                L->data[j] = tem;
            }
        }
    } while (step > 1);
}

堆排序

void heapAdjust(Sqlist *L, int n, int m){
    int tem, i;
    tem = L->data[n];
    for (i = 2 * n; i <= m; i*=2) {
        if (i < m && L->data[i] < L->data[i+1]) {
            i++;
        }
        if (tem >= L->data[i]) {
            break;
        }
        L->data[n] = L->data[i];
        n = i;
    }
    L->data[n] = tem;
}

void heapSort(Sqlist *L){
    for (int i = L->length/2; i >= 1; i--) {
        print(*L);
        heapAdjust(L, i, L->length);
    }
    
    for (int i = L->length; i > 1; i--) {
        swap(L, 1, i);
        heapAdjust(L, 1, i-1);
    }
}

归并排序

void mergeData(int sourceData[], int newData[], int low, int mid, int high){
    int lowInFirstArray = low;
    int lowInSecondArray = mid+1;
    int indexInNewArray = low;
    //将两个有序数组合并
    for (; lowInFirstArray <= mid && lowInSecondArray <= high; indexInNewArray++) {
        if (sourceData[lowInFirstArray] < sourceData[lowInSecondArray]) {
            newData[indexInNewArray] = sourceData[lowInFirstArray];
            lowInFirstArray++;
        } else {
            newData[indexInNewArray] = sourceData[lowInSecondArray];
            lowInSecondArray++;
        }
    }
//    printf("i:%d, j:%d, k:%d\n", lowInFirstArray, lowInSecondArray, indexInNewArray);
    //将两个数组剩余的部分加入尾部
    if (lowInFirstArray <= mid) {//前数组有剩余
        for (int i = 0; i <= mid - lowInFirstArray; i++) {
            newData[indexInNewArray + i] = sourceData[lowInFirstArray+i];
        }
    }
    if (lowInSecondArray <= high) {//后数组有剩余
        for (int i = 0; i <= high - lowInSecondArray; i++) {
            newData[indexInNewArray + i] = sourceData[lowInSecondArray+i];
        }
    }
}

void mergeAdapt(int sourceData[], int newData[], int low, int high){
    if (low == high) {
        newData[low] = sourceData[low];
    } else {
        int mid = (low + high)/2;
        int tempData[1000] = {0};
        
        mergeAdapt(sourceData, tempData, low, mid); //递归
        printData(tempData, 9);//打印tempData

        mergeAdapt(sourceData, tempData, mid+1, high);//递归
        
        printData(tempData, 9);//打印tempData
        mergeData(tempData, newData, low, mid, high);//合并
    }
}

void mergeSort(Sqlist *L){
    mergeAdapt(L->data, L->data, 1, L->length);
}

下图打印了整个tempData在归并的过程中的变化

归并排序

快速排序

int findPrior(Sqlist* L, int left, int right){
    int low = left;
    int high = right;
    int prior = L->data[left];//选定第一个作为默认中轴，可以优化
    while (low < high) {
        while (low < high && L->data[high] >= prior) {//如果high >= 中轴 则high--
            high--;
        }
        swap(L, low, high);//将小值前沉

        while (low < high && L->data[low] <= prior) {//low <= 中轴 则 low++
            low++;
        }
        swap(L, low, high);//将大值后沉
    }
    return low;
}



void qSort(Sqlist *L, int left, int right){
    if (left < right) {
        int prior = findPrior(L, left, right);
        qSort(L, left, prior - 1);
        qSort(L, prior + 1, right);
    }
}


void quickSort(Sqlist* L){
    qSort(L, 1, L->length);
}