经典算法

插入

  • 直接插入

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    void insertion_sort(int arr[], int len){
    	for(int i=1; i<len; i++){
    		int key = arr[i];	//存入当前元素 
    		int j = i-1;
    		while(j>=0 && key<arr[j]){	//后面比前面小
    			arr[j+1] = arr[j];
    			j--;
    		}
    		arr[j+1]=key;	//否则直接插在后面
    	}
    }

  • 折半插入

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    void BInsertSort(SqList &L){
    	for(i=2; i<=L.length; ++i){
    		L.r[0] = L.r[i];	//L.r[i]暂存到L.r[0]
    		low = 1; high = i-1;
    		while(low < high){
    			m = (high+low) / 2;
    			if(L.r[0].key < L.r[m].key) high = m-1;	//低半区
    			else low = m+1;	//高半区
    		}//while
    		for(j = i-1; j>=high+1; --j) L.r[j+1] = L.r[j];//high+1是插入位置
    		L.r[high+1] = L.r[0];
    	}//for
    }

    减少比较次数，但没有减少移动次数

  • shell排序

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    void shell_sort(int arr[], int len) {
    	int gap, i, j;
    	for(gap = len>>1; gap>0; gap >>= 1)
    		for(i=gap; i<len; i++) {
    			arr[0] = arr[i];//暂存在arr[0]
                for(j = i-gap; j>=0 && arr[j]>arr[0]; j -= gap)
                	//i-gap相当于该组上一个元素，j<0则找到插入位置
                	arr[j+gap] = arr[j];
                arr[j+gap] = arr[0];//插入
    		}
    }

交换

  • 冒泡排序

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    void bubble_sort(int arr[], int len) {
        int i, j;
        for (i = 0; i < len - 1; i++)
        {
            int flag = 0;
            for (j = 0; j < len - 1 - i; j++)
                if (arr[j] > arr[j + 1]){
                  flag = 1;
                  swap(arr[j], arr[j + 1]);
                }
            if(flag == 0)break;
        }
    }

  • 快排

    算法分析：时间复杂度O($nlogn$)， 其中选中心点是n，快排是$logn$，空间复杂度是O($logn$)，最坏是O(n)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    void quick_sort(int q[], int l, int r)//分治思想
    {
    	if (l>=r) return;

    	int i = l - 1, j = r + 1, x = q[l + r >> 1];
        while (i<j)//分段
        {
            do i ++ ; while (q[i] < x);
            do j -- ; while (q[j] > x);
            if(i < j) swap(q[i], q[j]);
        }
        quick_sort(q, l, j);
        quick_sort(q, j+1, r);//左右两段分别递归排序
    }

选择

  • 简单选择

    算法思想：0–i-1对当前的i都先让min=i，遍历i后面的所有值，若找到比i小的那么就更新min，并交换它们两个

    分析：需要进行的比较次数与初始状态下待排序的记录序列的排列情况无关，都是(n-1)n/2次，需要移动记录的次数最多为3(n-1)次

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    void selection_sort(int arr[], int len)
    {
    	int i,j;
    	for(i = 0; i<len-1; i++){
    		int min = i;
    		for(j = i+1; j<len; j++)	//走访未排序的元素
    			if(arr[j] < arr[min]) min = j;
    			swap(arr[j], arr[min]);
    	}
    }

  • 堆排序

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    //以大根堆为例
    //筛选
    void HeapAdjust(int arr[], int s, int m) {
    	cur = arr[s];
    	for(j=2*s; j<m; j*=2){
    		if(j < m && arr[j]<arr[j+1]) ++j;//if语句成立说明右子树比左子树大，j为较大的数
    		if(cur >= arr[j])break;//已经根最大
    		arr[s] = arr[j]; s = j; //交换
    	}
    	arr[s] = cur;
    }

    void HeapSort (int arr[]) {
    	//建堆
    	for(i = len/2; i>0; --i)	//从最后一个非叶子结点开始
    		HeapAdjust(arr, i, len);
    	for(i = len; i>1; --i){
    		swap(arr[1], arr[i]);//最后一个叶子和根交换-->放后面排序
    		HeapAdjust(arr, 1, len-1);	//重新调整为大顶堆
    	}
    }

归并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void merge_sort(int q[], int l, int r)
{
    if (l>=r) return;

    int mid = l + r >> 1;
    merge_sort(q, l, mid);//左右两边递归排序
    merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;//k为tmp数组中的索引
    while (i <= mid && j <= r)//两边都还没到头
        if(q[i] <= q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];

    while (i<=mid) tmp[k++] = q[i++];//把剩余没比较的直接复制
    while (j<=r) tmp[k++] = q[j++];

    for (i=l, j=0; i<=r; i++, j++) q[i] = tmp[j];
}

基数排序

实用于多个关键字情况 O(n)