排序算法

常见的排序算法练习

冒泡排序:

从小到大:
取数据A[0]将其与其后面的数据A[1]、A[2]、A[3]…等数据比较,遇到比A[0]更小的数就交换数值,再继续用A[0]和后面的数据比较,这样下来A[0]一定是这组数中最小的了。之后再取A[1]、A[2]、A[3]…等数据比较,和A[0]一样,A[1]最后成为剩下数据中最小的那一个…如此往复,直到排序结束。

Code:

template<typename T, unsigned char SIZE>
void Data<T, SIZE>::bubble_smalltobig()
{
    cout << "**********************Bubble:small to big*******************************" << endl;
    unsigned char i, j;

    /*遇到小的马上交换,交换后,用小的继续和下面的数比较,边比较(轮询)边换位*/
    for(i = 0; i < SIZE; i++)
    {
        for(j = i + 1; j < SIZE; j++)
        {
            if(data[i] > data[j])
            {
                /*i、j互换也可以实现交换*/
                data[j] ^= data[i];
                data[i] = data[j] ^ data[i];
                data[j] ^= data[i];
            }        
        }
    }

    for(i = 0; i < SIZE; i++)
    {
        cout << data[i] << " ";
    }

    if(i == SIZE)
    {
        cout << endl;
    }    
}

选择排序:

从大到小:
取数据A[0],记录其下角标‘0’,并将其与后面的数据A[1]、A[2]、A[3]…等数据进行比较,遇到比A[0]更小的数则将A[0]的下角标记录并替换掉,继续用新的A[新下角标值]和后面的A[5]、A[6]、A[7]等数据比较,有更小的数则同样记录并替换,最后得到一个最小数据对应的下角标,如果这个下角标和‘0’不同,则进行交换,至此A[0]中将是这组数据中最小的一个。接着对A[1]也进行新一轮的判别,记录下角标‘1’…..如此循环往复,直到排序完成。

Code:

template<typename T, unsigned char SIZE>
void Data<T, SIZE>::select_bigtosmall()
{
    cout << "****************************Select:big to small**********************************" << endl;

    unsigned char i,j;
    unsigned char note = 0;//记录最大数的下角标

    /*先轮询一边,记录最大的数的下角标,之后在换位*/
    for(i = 0; i < SIZE ; i++)
    {
        note = i;
        for(j = i + 1; j < SIZE; j++)
        {
            if(data[note] < data[j])
                note = j;
        }
        if(note != i)
        {
            data[i] ^= data[note];
            data[note] = data[i] ^ data[note];
            data[i] ^= data[note];
        }
    }

     for(i = 0; i < SIZE; i++)
    {
        cout << data[i] << " ";
    }

    if(i == SIZE)
    {
        cout << endl;
    }
}

插入排序:

从大到小:
数据A:45 35 84 1 36
首先假设45是已经排好序的,则取35,和A[0]比较,比45小则不动作,此时45和35也已经可以看做是一个从大到小的小的排序序列了45 35 84 1 36
然后再取84先和A[0]比较,发现84比A[0]大,则进行移位排序,排序后序列为84 45 35 1 36
再取1和A[0]比较,比84小,不触发排序,和A[1]比较,同样也不触发排序,和A[2]比较,依然没有触发排序,所以1原地不动84 45 35 1 36
再取36,和A[0]比较,比84小,不触发排序,和A[1]比,还是小,不触发排序,和A[2]比,比35大,触发排序移位,注意此时已经没有必要再和35后面的数比较了,因为35已经是之后的一段数中最大的了,所以要用break,最后84 45 36 35 1至此完成排序

Code:

template<typename T, unsigned char SIZE>
void Data<T, SIZE>::insert_bigtosmall()
{
    cout << "*************************Insert:big to small*************************" << endl;
    int i,j,k = 0;
    T temp;

    /*取一个数去和可能插入的左方的数比较,如果该数大于左方的被比较数则移位,因为保证了之前就是大到小排列,所以排完一次就break*/
    for(i = 1; i < SIZE; i++)
    {
        temp = data[i];

        for(j = 0; j < i ; j++)
        {
            if(data[i] > data[j])
            {
                for(k = i - 1; k >= j; k--)
                {
                    data[k+1] = data[k];
                }
                data[j] = temp;
                break;
            }
        }
    }

    for(i = 0; i < SIZE; i++)
    {
        cout << data[i] << " ";
    }

    if(i == SIZE)
    {
        cout << endl;
    }
}

快速排序:

1、定中轴(一般取第一个数)
2、从后往前:找出后面更小的数放前面(第一个数处),同时前面的下角标自加
3、从前往后:找出前面更大的数放后面(最后一个数处),同时后面下角标自减
4、递归调用:利用中轴,分别进行前后两边的排序,递归结束条件 high<=low

Code:

unsigned char quick(int *a, unsigned char low, unsigned char high)
{
    int temp = 0;
    temp = a[low];
    while(low < high)
    {
        /*从后面开始找出小的放前面*/
        while(low < high && a[high] >= temp)
        {
            high--;
        }

        if(low < high)
        {
            a[low] = a[high];
            low++;
        }

        /*从前面开始找出大的放后面*/
        while(low < high && a[low] < temp)
        {
            low++;
        }

        if(low < high)
        {
            a[high] = a[low];
            high--;
        }
        a[low] = temp;
    }
    return low;
}

void quicksort(int a[], unsigned char low, unsigned char high)
{
    unsigned char temp = 0;

    if(low < high)
    {
        temp = quick(a, low, high);//先分两半
        quicksort(a, temp+1, high);//对后半部分排序
        quicksort(a, low, temp-1);//对前半部分排序
    } 
}