排序

1. 冒泡排序（n^2）

每次交换把当前剩余元素中最大的元素移动到一端，剩余元素不断交换直至剩余元素为0

// 从小到大排序
void bubbleSort(int a[], int n){
    for(int i=1; i<n; i++){
        for(int j=0; j<n-i; j++){
            if(a[j]>a[j+1]){
                int temp = a[j+1];
                a[j+1] = a[j];
                a[j] = temp;
            }
        }
    }
}

2. 简单选择排序（n^2）

每次将当前剩余元素中最小的元素与剩余元素的第一个元素交换，直至剩余元素为0

// 从小到大排序
void selectSort(int a[], int n){
    for(int i=0; i<n; i++){
        int k = i;
        for(int j=i; j<n; j++){
            if(a[j]<a[k])
                k = j;
        }
        int temp = a[k];
        a[k] = a[i];
        a[i] = temp;
    }
}

3. 直接插入排序（n^2）

数列分为前面有序、后面无序两部分，每次将第一个无序的数插入到前面有序数列中，直至剩余无序元素为0

// 从小到大排序
void insertSort(int a[], int n){
    for(int i=1; i<n; i++){
        int temp = a[i], j = i;
        while(j>1 && temp<a[j-1]){
            a[j] = a[j-1];
            j--;
        }
        a[j] = temp;
    }
}

4. 两路归并排序

// 合并有序序列
const int maxn=100;
void merge(int a[], int L1, int R1, int L2, int R2){
    int i=L1, j=L2;
    int tmp[maxn], index=0;
    while(i<=R1 && j<=R2){
        if(a[i]<=a[j]) tmp[index++]=a[i++];
        else tmp[index++]=a[j++];
    }
    while(i<=R1) tmp[index++]=a[i++];
    while(j<=R2) tmp[index++]=a[j++];
    for(i=0;i<index;i++){
        a[L1+i]=tmp[i];
    }
}
// 递归实现
void mergeSort(int a[], int left, int right){
    if(left<right){
        int mid=(left+right)/2;
        mergeSort(a, left, mid);
        mergeSort(a, mid+1, right);
        merge(a, left, mid, mid+1, right);
    }
}
// 非递归实现
void mergeSort(int a[]){
    for(int step=2;step/2<=n;step*=2){
        for(int i=1;i<=n;i+=step){
            int mid=i+step/2-1;
            if(mid+1<=n){
                merge(a,i,mid,mid+1,min(i+step-1,n));
            }
        }
    }
}

4.1. 递归实现

5. 快速排序（nlogn）

// 对区间 [left, right] 进行划分，使得 a[left] 左边的数都小于它，右边的数都大于它
int partition(int a[], int left, int right){
    int tmp=a[left];
    while(left<right){
        while(left<right && A[right]>tmp) right--;
        A[left]=A[right];
        while(left<right && A[left]<tmp) left++;
        A[right]=A[left];
    }
    A[left]=tmp;
    return left; // 返回相遇的下标
}
// 快速排序
void quickSort(int a[], int left, int right){
    if(left<right){
        int pos=partition(a,left,right);
        quickSort(a,left,pos-1);
        quickSort(a,pos+1,right);
    }
}

6. ChangeLog

2018.08.25 初稿

2018.09.03 添加归并排序和快速排序