选择排序和快速排序

发表评论
12,667 views

A+

阳光明媚的一天，狄霸哥有点儿想出去走走，毕竟一连7天7夜躲在自己造的豪华大别墅里面。要不是外面的太阳明媚无比，咕咕咕，好吧，要不是肚子饿了，没有存粮了，我才不出去呢？豪华大别墅爽到爆炸啊！

狄霸哥走在街道上，看着街上的美食框框的流口水，他走进了一家豪华的大旅馆，吆喝小二过来，豪气对问小二这里有什么好吃的。小二说：口水鸡，黄金猪蹄，麻婆豆腐.....!狄霸哥：我不知到哪个好吃的，这样吧，简单一点，全部都给我上一份吧！我这人做事就喜欢简单！小二：好嘞！这位客官。

吧唧吧唧，吃得走不动的狄霸哥实在是吃不下了，准备买单的时候，呃，没有带钱。但是狄霸哥一点都不慌，利用程序之力绘制出大量的金币，叫小二过来买单，摔出大量的金币，亮瞎了小二的眼睛。看着小二一脸懵逼，狄霸哥洋洋得意。突然，小二：老板，这里有人用假币。棒棒棒，来了一群人，把狄霸哥围了起来，这下狄霸哥蒙蔽了，恨自己没学到家啊！

善良的老板没有用武力解决问题，而是甩出了一大本记账本，里面有所有客户的消费累计，但是没有排序好，要狄霸哥将这个由低到高的排序一下。仁慈的老板说了也就10W个客户罢了。苦逼的狄霸哥一脸惆怅，突然他想到了选择排序。

选择排序

选择排序，通过对比每一个元素来选择一个合适的数据来放置在合适的位置上。一个很简单的排序算法。

static void SortChoice(int[] datas)
{
    int length = datas.Length;

    int index = 0;
    for (int i = 0; i < length; i++)
    {
        index = i;
        for (int j = i + 1; j < length; j++)
        {
            if (datas[j] < datas[index])
            {
                //选取更合适原来位置的值
                index = j;
            }
        }

        if (index != i)
        {
            //有更合适这个位置的数，进行交换
            int temp = datas[i];
            datas[i] = datas[index];
            datas[index] = temp;
        }
    }
}

static void SortChoice(int[] datas)

{

int length = datas.Length;

int index = 0;

for (int i = 0; i < length; i++)

{

index = i;

for (int j = i + 1; j < length; j++)

{

if (datas[j] < datas[index])

{

//选取更合适原来位置的值

index = j;

}

if (index != i)

{

//有更合适这个位置的数，进行交换

int temp = datas[i];

datas[i] = datas[index];

datas[index] = temp;

}

在SortChoice函数中，有一个嵌套的循环，其中内层循环是从i+1开始的，i表示的是要对比的元素，i+1开始，表示只对比后面的元素，因为前面的已经比较过了

例如：5 1 3 9，一、首先比较 5 和 1，发现1小，所以交换，变为 1 5 3 9。二、再比较1 和 3，比较1 和 9，都比1大，不用交换，变为：1 5 3 9，此时你可以发现1这个元素已经和所有的元素都对比过了，所以下轮循环就没必要再和前面元素对比了。三、进行对比 5 和 3 ，3小，交换，变为：1 3 5 9。四、继续对比3和9，5和9，好了排序好了

选择排序的层层对比数是递减的，由n-1递减到1，所以执行时间为（n-1+1）* n/2 = O(n^2)。哒哒哒，狄霸哥等了几十秒了，所有用户的数据才排序好，不耐烦的狄霸哥很是嫌弃，想要更快的解决办法。突然狄霸哥想到了快速排序。

快速排序

快速排序是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

static List<int> quickSort(List<int> datas) {
    int length = datas.Count;
    if (length < 2) {
        return datas;
    }

    //随机一个参考数
    Random r = new Random();
    int random_index = r.Next(0, length);
    int val = datas[random_index];
    datas.RemoveAt(random_index);
    List<int> left = new List<int>();
    List<int> right = new List<int>();

    foreach (int data in datas) {
        if (data < val)
        {
            left.Add(data);
        }
        else {
            right.Add(data);
        }
    }

    left = quickSort(left);
    right = quickSort(right);
    left.Add(val);
    left.AddRange(right);

    return left;
}

static List<int> quickSort(List<int> datas) {

int length = datas.Count;

if (length < 2) {

return datas;

}

//随机一个参考数

Random r = new Random();

int random_index = r.Next(0, length);

int val = datas[random_index];

datas.RemoveAt(random_index);

List<int> left = new List<int>();

List<int> right = new List<int>();

foreach (int data in datas) {

if (data < val)

{

left.Add(data);

}

else {

right.Add(data);

}

left = quickSort(left);

right = quickSort(right);

left.Add(val);

left.AddRange(right);

return left;

}

主要思想就是每个大块都分成分成3块，直到不能分为止，数组只有一个元素或者没有，其中一块就是中间那块（参考值），把比参考值小的放在左边，大的放在右边，然后继续对左边的也这样做，右边的也这样做，最后分成了n块，直到每一块都是排好序的（只有一个元素或则没有，当然是排好序的了），而且都是通过参考值来排好序的，所以合并起来，就排好了

例如：5 1 3 9，随机参考值为5，分为3块：1 3，5，9。再对左右边执行分块，右边只有一个元素，所以直接返回，左边为：1 3，随机参考数为：1，3比1大所以放在右边，左边为空，此时3块为：null，1，3。再对左右边进行分割，左边为空，右边只有一个，所以直接返回。不能再分割了，进行合并操作，从栈顶开始，null,1,3合并为：1 3。再进行1 3，5，9合并，最总得到：1 3 5 9

快速排序的运行时间为O(nlog(n))，运气不好的话，其实也是O(n^2)。这次狄霸哥很是满意，几百毫秒不到一秒钟就完成排序了。这里采用了集合来管理元素分组，这样也比较明确快速排序的思想。可能是这拖慢了速度，不然其实几十毫秒就能完成。可以去我的笔记那里看不用List的办法。

一般来说，数据库等代码等的排序都是使用的快速排序算法，快速排序算法的优势在数据量越来越大的时候具有更显著的效果，而选择排序只适合在数据量小的情况下使用。

狄霸哥拿着已经排好序的账本，甩到了旅馆老板的脸上。旅馆老板一脸懵逼的看着已经排好序的账本，打呼一声：大神！在众多诧异的眼光下，狄霸哥潇洒的走出了旅馆门口，这样就吃了个霸王餐，真是爽！

选择排序

快速排序

发表评论取消回复

登录 注册 找回密码

登录注册找回密码