手记

C++实现之快速排序的两种不同做法

快速排序(C++实现)

快速排序在我们程序的世界当中是非常常见的;在以后的应聘当中更是一道基本上必考的排序题;
那么快速排序有两种写法;其实这两种写法本质是一样的;只是第二种写法更为通俗易懂;

写法一:

#include <iostream>

using namespace std;

void quickSort(int* arr, int start, int end)
{
    if (start < end)
    {
        int i = start, j = end;
        while (i < j)
        {
            while (arr[i] <= arr[j] && i < j)
            {
                j--;
            }
            if (i < j)
            {
                arr[i] = arr[i] ^ arr[j];
                arr[j] = arr[i] ^ arr[j];
                arr[i] = arr[i] ^ arr[j];
                i++;
            }
            while (arr[i] < arr[j] && i < j)
            {
                i++;
            }
            if (i < j)
            {
                arr[i] = arr[i] ^ arr[j];
                arr[j] = arr[i] ^ arr[j];
                arr[i] = arr[i] ^ arr[j];
                j--;
            }
        }
        quickSort(arr, i + 1, end);
        quickSort(arr, start, i - 1);
    }
}

int main()
{
    int arr[] = {
        2, 9, 4, 3, 8, 6, 2, 1, 5, 4, 7, 3, 8, 4, 9 , 3, 5, 2
    };
    quickSort(arr, 0, 17);
    for (int i = 0; i < 18; i++)
    {
        cout << arr[i] << "   ";
    }
    cout << endl;
    return 0;
}

写法二:

#include <iostream>

using namespace std;

void quickSort(int* arr, int start, int end)
{
    if (start < end)
    {
        int i = start, j = end, store = arr[start];
        while (i < j)
        {
            while (i < j && arr[j] >= store)
            {
                j--;
            }
            if (i < j)
            {
                arr[i] = arr[j];
            }
            while (i < j && arr[i] < store)
            {
                i++;
            }
            if (i < j)
            {
                arr[j] = arr[i];
            }
        }
        arr[i] = store;
        quickSort2(arr, i + 1, end);
        quickSort2(arr, start, i - 1);
    }
}

int main()
{
    int arr[] = {
        2, 9, 4, 3, 8, 6, 2, 1, 5, 4, 7, 3, 8, 4, 9 , 3, 5, 2
    };
    quickSort(arr, 0, 17);
    for (int i = 0; i < 18; i++)
    {
        cout << arr[i] << "   ";
    }
    cout << endl;
    return 0;
}

解析:

我们知道快速排序就是每一次以其中某一个数为中心;将大于它的所有的数放在后面;将小于它的所有数都放在它的左边;当然等于它的数左右皆可;

那么方法一是将这个指定的中心数(一般以第一个或最后一个为主)每一次的比较不合适之后都要进行换位;而且换的人头晕眼花的;如不细细琢磨和想象真的是会奔溃的;第二种方法则是显式的定义出来;这样这样就有个好处;不用每次比较不合适之后就去来回的交换位置(我们知道交换位置也是很浪费系统资源的);不过这里的使用的是异或交换法;效率最高;但主要是方法一不通俗,晦涩难懂;

注意方法二在完成一次大的比较之后(也就是一次递归执行之前)要将那个“空位”填补上;那么就是什么呢?就是之前我们定义的那个中心数;因为所有小于或等于的数都在它的左边,所有大于它的数都在它的右边;而中间(不一定是绝对的中间)的那个所谓的“空位”(其实是有数,只是对换到最后留下来的)就是那个中心数的位置;

不知道大家理解了没有;希望能对大家有帮助;最后附上运行结果图一张;

运行结果:

3人推荐
随时随地看视频
慕课网APP