快速排序的分析与实现

发布时间:2020-09-17 00:44:29 作者:清幽宁
来源:网络 阅读:258

快速排序是一种使用性非常强的排序算法,虽然它最坏的情况下时间复杂度O(N^2),但平均时间复杂度是O(N*logN),并在内存的使用、程序算法的复杂性上表现优秀,尤其是对快速排序进行随机化的可能,快速排序是最使用的一种算法之一。

  算法思想:

    1.创建一个临时变量,把数组中最右边的值保存起来,最右边就形成一个坑。

    2.然后找左边大于临时变量的那个值放到坑里,这样左边会形成新的坑。

    3.在找右边小于临时变量的那个值放到新的坑里,就这样一直找。

    4.知道找完,最后把临时变量放到最后形成的那个坑里。

    5.在把这个数组分成两个子序列,特点:左边的子序列中的数小于等于右边的子序列中的数。

    6.在通过递归调用,来排序子序列。

    5.知道子序列排完,然后合并。(由于子序列是就地序列,所以合并不需要操作,排序已经完成)

实现代码:

Sort.h中

int SingleSort(int *a, int left, int right)
{
    assert(a);
  int tmp = a[right];//临时变量保存值
        while (left < right)
     {
           //找左边大于等于tmp的数
              while (left < right&&tmp >= a[left])
          {
                   left++;
             }
           if (left < right)
                {
                   a[right--] = a[left];//把值给右边,然后--
           }
           //找右边小于等于tmp的值
              while (left < right&&tmp <= a[right])
         {
                   right--;
            }
           if (left < right)
                {
                   a[left++] = a[right];//把值给左边,然后++
           }
   }
   a[left] = tmp;
      return left;
}
void QuickSort(int *arr, int left, int right)
{
     if (arr == NULL)
    {
           return;
     }
   if (left < right)
        {
           //递归调用
              int div = SingleSort(arr, left, right);
             QuickSort(arr, left, div - 1);
              QuickSort(arr, div + 1, right);
     }
}
//打印函数
void Print(int *arr, int size)
{
     for (int i = 0; i < size; i++)
   {
           cout << arr[i] << " ";
  }
   cout << endl;
}

test.cpp中

#include<iostream>
using namespace std;
#include "Sort.h"

void Test()
{
  int arr[] = { 3, 9, 7, 6, 1, 2, 4, 8, 0, 5 };
       QuickSort(arr, 0,sizeof(arr) / sizeof(arr[0])-1);
   Print(arr, sizeof(arr) / sizeof(arr[0]));
}
int main()
{
   Test();
     system("pause");
    return 0;
}

  我曾经看过看过一篇博客,快速排序对小范围数字排序会花费很多时间,通过我查询资料得知,数字总量小于13,用直接插入排序表较好,超过这个数字用快速排序。然后我就把代码改了一下.

//直接插入排序
void InsertSort(int *a, int size)
{
        int end;
    int tmp;
    for (int i = 0; i < size - 1; i++)
       {
           end = i;
            tmp = a[end + 1];
           while (end >= 0 && tmp<a[end])
                {
                   a[end + 1] = a[end];
                        end--;
              }
           a[end + 1] = tmp;
   }
}
void QuickSort(int *arr, int left, int right)
{
        if (arr == NULL)
    {
           return;
     }
   if (right < 13)
  {
           InsertSort(arr, right + 1);
 }
   else
        {
           if (left < right)
                {
                   //递归调用
                      int div = SingleSort(arr, left, right);
                     QuickSort(arr, left, div - 1);
                      QuickSort(arr, div + 1, right);
             }
   }
}

   上面的代码还不够好,如果快速排序是,你的运气比较差,每次取出的数都是最大或者最小,这样的话他就会变成最坏一种情况,时间复杂度为O(N^2),为了避免这种情况,我想到一种办法,三数取中法,

它是什么意思?

   三个数分别为最左边,最右边,中间这三个数,取得话,就取既不是最大也不是最小的这个数,这样就能避免上面那种情况。

//三数取中
int Mid(int *a, int left, int right)
{
        int mid = left - (left - right);
    if (a[left] < a[right])
  {
           if (a[left]>a[mid])
              {
                   return a[left];
             }
           else if (a[right] < a[mid])
              {
                   return a[right];
            }
           else
                {
                   return a[mid];
              }
   }
   else
        {
           if (a[right] > a[mid])
           {
                   return a[right];
            }
           else if (a[left] < a[mid])
               {
                   return a[left];
             }
           else
                {
                   return a[mid];
              }
   }
}
int SingleSort(int *a, int left, int right)
{
  assert(a);
  int tmp = Mid(a,left,right);//临时变量保存值,三数取中
  while (left < right)
     {
           //找左边大于等于tmp的数
              while (left < right&&tmp >= a[left])
          {
                   left++;
             }
           if (left < right)
                {
                   a[right--] = a[left];//把值给右边,然后--
           }
           //找右边小于等于tmp的值
              while (left < right&&tmp <= a[right])
         {
                   right--;
            }
           if (left < right)
                {
                   a[left++] = a[right];//把值给左边,然后++
           }
   }
   a[left] = tmp;
      return left;
}

这样就比较完善了,如果我不想用递归,该这么办那?然后我就想到了借助栈来实现。

void QuickSort(int *arr, int left, int right)
{
   stack<int> s;
 s.push(left);//压栈数组的左下标
     s.push(right);//压栈数组的有下标
    while (!s.empty())
  {
           int tmpRight = s.top();
             s.pop();
            int tmpLeft = s.top();
              s.pop();
            //把数组排序成左区间的数小于等于有区间的数
              int div = SingleSort(arr, tmpLeft, tmpRight);
               //压栈左区间的左右两个数的下标
            if (tmpLeft < div - 1)
           {
                   s.push(tmpLeft);
                    s.push(div - 1);
            }
           //压栈右区间的左右两个数的下标
             if (div + 1 < tmpRight)
         {
                   s.push(div + 1);
                    s.push(tmpRight);
           }
   }
}

  写到这里,我有想到了另一种实现SingleSort()函数的方法,感觉比上面的更简单,不过理解起来比较抽象。

    思想:

     1.定义一个cur为a[0]位置的下标

     2.在定义一个prev为a[0]的前一个位置。

     3.当a[0]位置的值小于最右边的值。

     4.++prev,然后交换prev和cur对应的值。

     5.如果小于最右边的值,++prev,prev和最右边值交换。

     6.一直进行下去,就会让左边的值小于等于右边的值。

int SingleSort(int *arr, int left, int right)
{
       int cur = left;
     int prev = cur - 1;
 int key = Mid(arr, left, right);
    swap(arr[right], key);//把key的值放到最右边
 while (cur < right)
      {
           //++prev != cur防止自己和自己交换
            if (arr[cur]<=arr[right]&&++prev != cur)
         {
                   swap(arr[prev], arr[cur]);
          }
           cur++;
      }
   swap(arr[++prev], arr[right]);
      return prev;
}


推荐阅读:
  1. 快速排序的python实现
  2. 快速排序的多种思路实现

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

程序

上一篇:Python hashlib常见摘要算法详解

下一篇:如何更快乐的使用Java 8中的Lambda特性

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》