排序算法

浏览数：33 / 时间：2015年06月08日

冒泡排序：泡泡（最小值）从底部冒上来

void bubblesort(int *arr, const int len)
{
    if(arr == NULL)
        return;
    for(int i = 0; i <len - 1; i++) {
        for(int j = len-2; j>= i; j--) {
            if(arr[j] > arr[j+1])
                swap(arr[j],arr[j+1]);
        }
    }
}

选择排序：从当前开始，选择从后一个元素开始的其余所有元素中的最小值，交换，使最小值到前面。

void selectsort(int * arr, const int len)
{
    if(arr == NULL)
        return;
    for(int i = 0; i < len - 1; i++){
        int min = i;
        for(int j = i+1; j < len; j++) {
            if(arr[min] > arr[j])
                min = j;
        }
        if(i != min)
            swap(arr[i],arr[min]);
    }
}

简单插入排序：如果当前元素i比前面的元素小，将当前元素插入到前面合适的位置中

void insertsort(int *arr, const int len)
{
    if(arr == NULL)
        return;
    for(int i = 1; i < len; i++){
        if(arr[i] < arr[i-1]) {
            int temp = arr[i];
            int j = i-1;
            for(;arr[j] > temp; j--) 
                arr[j+1] = arr[j];
            arr[j+1] = temp;
        }
        
    }
}

堆排序：

void heapsort(int *arr, const int len) 
{
    if(arr == NULL)
        return;
    int i = 0;
    for(i = len/2;i >= 0; i--) {
        heapadjust(arr,len,i,len-1);//第一次调整，把大的元素放到父节点
    }
    for(i = len-1; i > 0;i--) {
        swap(arr[i],arr[0]);//交换第一个和最后一个元素
        heapadjust(arr,len,0,i-1);//调整余下的元素。由于前面已经调整过了，所以从0开始，然后选择元素较大的分支，得到这些元素中的最大值
    }
}

//把大的数字调整到父节点
void heapadjust(int *arr, const int len, int s, int m)
{
    int temp = arr[s];
    for(int j = 2*s; j <= m; j *= 2){
        if(j < m && arr[j] < arr[j+1])
            ++j;
        if(temp >= arr[j])
            break;
        arr[s] = arr[j];
        s = j;
    }
    arr[s] = temp;
}

归并排序：归并过程很重要

void mergesort(int *arr, const int len)
{
    msort(arr,arr,0,len-1);
}

void msort(int *sr,int *tr1,int s, int t)
{
    int m;
    int tr2[arr_len];
    if(s == t) 
        tr1[s] = sr[s];
    else {
        m = (s+t)/2;
        msort(sr,tr2,s,m);
        msort(sr,tr2,m+1,t);
        merge(tr2,tr1,s,m,t);
    }
}

void merge(int *sr, int *tr, int s, int m, int t)
{
    int i = s, j = m+1, k = s;
    for(; i <= m && j <= t; k++) {
        if(sr[i] < sr[j])
            tr[k] = sr[i++];
        else 
            tr[k] = sr[j++];
    }
    while(i <= m) {
        tr[k++] = sr[i++];
    }
    while(j <= t) {
        tr[k++] = sr[j++];
    }
}

快速排序

void quicksort(int *arr, const int len)
{
    qsort(arr,0,len-1);
}

void qsort(int *arr, int low, int high)
{
    if(low < high) {
        int pivot = partition(arr,low,high);
        qsort(arr,low,pivot-1);
        qsort(arr,pivot+1,high);
    }
}

int partition(int *arr, int low, int high)
{
    int pivotkey = arr[low];
    while(low < high) {
        while(low < high && arr[high] >= pivotkey )
            high--;
        swap(arr[low],arr[high]);
        while(low < high && arr[low] <= pivotkey)
            low++;
        swap(arr[low],arr[high]);
    }
    return low;
}