一、常见的排序算法

二、冒泡排序

思路:刚开始,从0到N-2每个跟他后面的比,比完后,如果大(小)交换位置,比完一轮后,确定最后一个位置

    接着,0到N-3重复。依次循环

特点:每次确定最后一个位置

代码:

void sort(int *a, int n)
{
    int t;
    for(int i = 0; i < n-1; i++)
    {
        for(int j = 0; j < n-1-i; j++)
        {
            if(a[j] > a[j+1])
            {
                t = a[j];
                a[j] = a[j+1];
                a[j+1] = t;
            }
        }
    }
}

三、选择排序

思路:每次从当前待排序中第二个到最后一个找最小(大),跟第一个换,确定第一个位置。

    接着,待排序为第二个到最后一个。依次循环。

特点:每次确定第一个位置

代码:

void sort(int *a, int n)
{
    for(int i = 0; i < n-1; i++)
    {
        int p = i, t;
        for(int j = i+1; j < n; j++)
        {
            if(a[p] > a[j])
                p = j;
        }
        t = a[p]; a[p] = a[i]; a[i] = t;
    }
}

四、插入排序

思路:维持一个有序的小序列(刚开始为第一个元素),一次插入一个元素。比较从有序序列的末尾开始,将想要插入的元素和已经有序的最大者开始比起,如果比它大则直接插入在其后面,否则一直往前找直到找到它该插入的位置。插入后,所有位置向后移位。

特点:第i轮前i个是有序的

代码:

void sort(int *a, int n)
{
    int i, j, t, e;
    for(i = 1; i < n; i++)
    {
        e = i-1; t = a[i];
        while(e >= 0 && a[e] > t)
        {
            a[e+1] = a[e];
            e--;
        }
        a[e+1] = t;
    }
}

五、快速排序(详解

思路:找一个基准点,让该点左边的元素都比他小(大), 右边的元素都比他大(小)。接着递归执行。

特点:略

代码:

int parttition(int *a, int l, int r)
{
    int i = l, j = r, x = a[l];
    while(i < j)
    {
        while(i < j && a[j] >= x) j--;
        if(i < j) a[i] = a[j];
        while(i < j && a[i] <= x) i++;
        if(i < j) a[j] = a[i];
    }
    a[i] = x;
    return i;
}
void quiksort(int *a, int l, int r)
{
    if(l < r)
    {
        int partitionIndex = parttition(a, l, r);
        quiksort(a, l, partitionIndex-1);
        quiksort(a, partitionIndex+1, r);
    }
}

六、归并排序

思路:将一段分成两段分别排序,然后在合并,递归。

特点:略

代码:

void merge(int *a, int l, int mid, int r)
{
    int x = l, y = mid+1, t = 0;
    int *tmp = new int[r-l+1];
    while(x <= mid && y <= r)
    {
        if(a[x] <= a[y]) tmp[t++] = a[x++];
        else tmp[t++] = a[y++];
    }
    while(x <= mid) tmp[t++] = a[x++];
    while(y <= r) tmp[t++] = a[y++];
    t = 0;
    while(l <= r) a[l++] = tmp[t++];
    delete tmp;
}
void sort(int *a, int n, int l, int r)
{
    if(l < r)
    {
        int mid = (l+r) / 2;
        sort(a, n, l, mid);
        sort(a, n, mid+1, r);
        merge(a, l, mid, r);
    }
}

代码(交换数组,使用了copy临时数组,初始值应该与data相同,减少复杂度):

void gb_sort(int *data, int *copy, int start, int end)
{
    if(start == end)
    {
        copy[start] = data[start];
        return;
    }
    int length = (end-start) / 2;
    gb_sort(copy, data, start, start+length);
    gb_sort(copy, data, start+length+1, end);
    int i = start+length, j = end, p = end;
    while(i >= start && j >= start+length+1)
    {
        if(data[i] > data[j]) copy[p--] = data[i--];
        else copy[p--] = data[j--];
    }
    while(i >= start) copy[p--] = data[i--];
    while(j >= start+length+1) copy[p--] = data[j--];
}

七、基数排序

思路:将整数按位数切割成不同的数字,然后按每个位数分别比较。对于每一位,按桶排序进行排序。

特点:略

代码:

int get_max(int a[], int n)
{
    int i, max;
    max = a[0];
    for (i = 1; i < n; i++)
        if (a[i] > max)
            max = a[i];
    return max;
}
void count_sort(int a[], int n, int exp)
{
    int output[n];
    int i, buckets[10] = {0};
    for (i = 0; i < n; i++)
        buckets[ (a[i]/exp)%10 ]++;
    for (i = 1; i < 10; i++)
        buckets[i] += buckets[i - 1];
    for (i = n - 1; i >= 0; i--)
    {
        output[buckets[ (a[i]/exp)%10 ] - 1] = a[i];
        buckets[ (a[i]/exp)%10 ]--;
    }
    for (i = 0; i < n; i++)
        a[i] = output[i];
}
void sort(int a[], int n)
{
    int exp;
    int max = get_max(a, n);
    for (exp = 1; max/exp > 0; exp *= 10)
        count_sort(a, n, exp);
}

八、希尔排序(详解

思路:希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少,速度很快;当元素基本有序了,步长很小, 插入排序对于有序的序列效率很高。步长可取3->2->1

特点:多次插入排序

代码:暂时略


九、堆排序(详解

思路:将待排序序列构造成一个大顶堆,此时,整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换,此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。如此反复执行,便能得到一个有序序列

特点:使用了完全二叉树

代码:

void adjust(int *a, int i, int n)
{
    int t = a[i];
    for(int k = i*2+1; k < n; k = k*2+1)
    {
        if(k+1<n && a[k] < a[k+1]) k++;
        if(a[k] > t)
        {
            a[i] = a[k];
            i = k;
        }else break;
    }
    a[i] = t;
}
void sort(int a[], int n)
{
    int t;
    for(int i = n/2-1; i >= 0; i--)
        adjust(a, i, n);
    for(int i = n-1; i > 0; i--)
    {
        t = a[0];a[0] = a[i];a[i] = t;
        adjust(a, 0, i);
    }
}

十、桶排序

思路:建立数组元素最大值的数组,用于计算每个元素出现的次数,然后遍历即可

特点:空间换时间

代码:

for(i=1;i<=n;i++)
{
    cin >> t;
    b[t]++;
}
for(i = maxN; i >= 0; i--)
    for(j = 1; j <= b[i]; j++)
        printf("%d ",i);

十一、计数排序(详解

思路:知道数组里有多少项小于或等于该元素。就能准确地给出该元素在排序后的数组的位置。

特点:略

代码:

int get_max(int a[], int n)
{
    int i, max;
    max = a[0];
    for (i = 1; i < n; i++)
        if (a[i] > max)
            max = a[i];
    return max;
}
void sort(int *a, int n)
{
    int k = get_max(a, n), sum = 0;
    int *c = new int[k+1], *b = new int[n];
    for(int i = 0; i < k+1; i++) c[i] = 0;//初始化c
    for(int i = 0; i < n; i++)
        c[a[i]] ++;
    for(int i = 1; i < k+1; i++)
        c[i] += c[i-1];
    for(int i = n-1; i >= 0; i--)
    {
        b[c[a[i]]-1] = a[i];
        c[a[i]]--;
    }
    for(int i = 0; i < n; i++)
        a[i] = b[i];
}


你可能感兴趣的文章

评论区

已有2位网友发表了看法:

1L 访客  2019-03-09 15:49:30 回复
好帖,收藏了
2L zc  2019-03-09 15:54:29 回复
(⊙v⊙)

发表评论

必填

选填

选填

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

您好,欢迎到访网站!
  查看权限

«   2019年3月   »
123
45678910
11121314151617
18192021222324
25262728293031