↓阿里云服务器3年不到300元↓

Tomcat 架构解析 阿里云服务器3年不到300元 Redis设计与实现

C++ 实现常见排序算法

#include <iostream>

#include <assert.h>

using namespace std;

void print_result(int a[], int n, char s=’ ‘)
{
for(int i=0; i<n; i++)
{
cout << a[i] << s;
}
cout << endl;
}

void insert_sort(int a[], int n)
{
assert(n > 1);

for(int i=1; i<n; i++)
{
    int j=0;
    while(j < i)  //find right position for a[i]
    {
        if(a[j] > a[i]) break;
        ++j;
    }
    if(j < i)
    {
        int tmp = a[i];
        for(int k=i; k>j; k--)
        {
            a[k]=a[k-1];
        }
        a[j]=tmp;
    }
}

}

void select_sort(int a[], int n)
{
assert(n > 1);

for(int i=0; i<n; i++)
{
    int k = i;    //find the right k
    for(int j=i+1; j<n; j++)
    {
        if(a[j] < a[k])
        {
            k = j;
        }
    }
    if(k != i)
    {
        int tmp = a[i];
        a[i] = a[k];
        a[k] = tmp;
    }
}

}

void buble_sort(int a[], int n)
{
assert(n > 1);

for(int i=1; i<n; i++)
{
    for(int j=0; j<n-i; j++) //move downwards the biggest element
    {
        if(a[j+1] < a[j])
        {
            int tmp = a[j];
            a[j] = a[j+1];
            a[j+1] = tmp;
        }
    }
}

}

void quick_sort(int* a, int left, int right)
{
if(left >= right)
{
return;
}

int slot_value = a[left];

int i=left, j=right;
while(i < j)
{
    while(a[j] > slot_value && j > i)
    {
        --j;
    }
    if(j > i)
    {
        a[i] = a[j];
        ++i;
    }

    while(a[i] < slot_value && i < j)
    {
        ++i;
    }
    if(i < j)
    {
        a[j] = a[i];
        --j;
    }
}

a[i] = slot_value;

quick_sort(a, left, i-1);
quick_sort(a, i+1, right);

}

int main()
{
if(1)
{
int a[] = {3, 9, 5, 11, 44, 93, 2, 65, 12, 34, 54, 13, 12, 22, 10, 67, 81, 25};
constexpr int size = sizeof(a)/sizeof(int);
print_result(a, size);

    cout << "insert_sort" << endl;
    insert_sort(a, size);
    print_result(a, size);
    cout << endl;
}

if(1)
{
    int a[] = {3, 9, 5, 11, 44, 93, 2, 65, 12, 34, 54, 13, 12, 22, 10, 67, 81, 25};
    constexpr int size = sizeof(a)/sizeof(int);
    print_result(a, size);

    cout << "select_sort" << endl;
    select_sort(a, size);
    print_result(a, size);
    cout << endl;
}

if(1)
{
    int a[] = {3, 9, 5, 11, 44, 93, 2, 65, 12, 34, 54, 13, 12, 22, 10, 67, 81, 25};
    constexpr int size = sizeof(a)/sizeof(int);
    print_result(a, size);

    cout << "buble_sort" << endl;
    buble_sort(a, size);
    print_result(a, size);
    cout << endl;
}

if(1)
{
    int a[] = {3, 9, 5, 11, 44, 93, 2, 65, 12, 34, 54, 13, 12, 22, 10, 67, 81, 25};
    constexpr int size = sizeof(a)/sizeof(int);
    print_result(a, size);

    cout << "quick_sort" << endl;
    quick_sort(a, 0, size-1);
    print_result(a, size);
    cout << endl;
}

return 0;

}

C++ Primer Plus 第六版 阿里云服务器3年不到300元 流畅的 Python