用递归实现的快速排序

快速排序的两种不同实现
服务器君一共花费了362.269 ms进行了5次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

快速排序是对冒泡排序的一种改进。它的基本思想是:通过一次排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一不部分的所有数据都要小,然后再按次方法对这两部分数据分别进行快速排序,整个排序过程可以递归或者非递归进行,以此达到整个数据变成有序序列。

下面是快速排序的递归实现:

#include "stdafx.h"
#define LIST_INIT_SIZE 100    //顺序表初始大小
#define LISTINCREMENT 10    //顺序表增量
typedef int ElemType;    //顺序表元素类型
typedef struct        //顺序表结构
{
    ElemType *elem;
    int length;
    int listsize;
}SqList;
//初始化顺序表
int InitList_Sq(SqList &L)        
{
    L.elem = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
    if(!L.elem) return -1;
    L.length = 0;
    L.listsize = LIST_INIT_SIZE;
    return 0;
}
//创建顺序表
int CreatList_Sq(SqList &L)
{
    InitList_Sq(L);
    int i = 1;
    while(scanf("%d",&L.elem[i]) != EOF)
    {
        i++;
    }
    L.length = i - 1;
    return 0;
}
//一趟快速排序
int Partition(SqList &L,int low,int high)
{
    L.elem[0] = L.elem[low];
    int pivotkey;
    pivotkey = L.elem[low];
    int temp;
    while(low < high)
    {
        while(low < high && L.elem[high] >= pivotkey) --high;;
        L.elem[low] = L.elem[high];
        while(low < high && L.elem[low] <= pivotkey) ++low;
        L.elem[high] = L.elem[low];
    }
    L.elem[low] = L.elem[0];
    
    return low;
}
//递归实现快速排序
void QuickSort(SqList &L,int low,int high)
{
    if(low < high)
    {
        int pivotloc = Partition(L,low,high);
        QuickSort(L,low,pivotloc - 1);
        QuickSort(L,pivotloc + 1,high);
    }
}
int _tmain(int argc, _TCHAR *argv[])
{
    SqList L;
    CreatList_Sq(L);
    QuickSort(L,1,L.length);
    for(int i = 1; i <= L.length; i++)
    {
        printf("%d ",L.elem[i]);
        if(LIST_INIT_SIZE == i) printf("\n");
    }
    char ch = getchar();
    
    return 0;
}

快速排序的非递归算法:

#include <iostream>
#include <stack>
using namespace std;
template <class T>
int partition(T a[],int low,int high)
{
 T v=a[low];
 while(low<high)
 {  
  while(low<high && a[high]>=v) high--;
  a[low]=a[high];
  while(low<high && a[low]<=v) low++;
  a[high]=a[low];
 }
 a[low]=v;
 return low;
 
}
 
template <class T>
void QuickSort(T a[],int p,int q)
{
 stack<int> st;
 int j;
 do{
      while(p<q)
      {
         j=partition(a,p,q);   
         if( (j-p)<(q-j) )
         {
            st.push(j+1);
            st.push(q);
            q=j-1;
         }
         else
         {
           st.push(p);
           st.push(j-1);
           p=j+1;
         }   
      }
  if(st.empty()) return;
  q=st.top();st.pop();  
  p=st.top();st.pop();  
  //cout<<endl<<"p:"<<p<<" ";
  //cout<<"q:"<<q<<endl;
 }while(1);
}
void main()
{
 //int a[7]={7,6,5,4,3,2,1};
 //int a[7]={1,2,3,4,5,6,7};
 int a[7]={3,5,2,3,66,225,1};
 for(int i=0;i<7;i++)
  cout<<a[i]<<" ";
 QuickSort(a,0,6);
 cout<<endl;
 for(int i=0;i<7;i++)
  cout<<a[i]<<" ";
}  

本文地址:http://www.nowamagic.net/librarys/veda/detail/1194,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/1194

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《编程珠玑(第2版)》 Jon Bentley (作者), 黄倩 (译者), 钱丽艳 (译者)

《编程珠玑(第2版)》是计算机科学方面的经典名著。书的内容围绕程序设计人员面对的一系列实际问题展开。作者Jon Bentley 以其独有的洞察力和创造力,引导读者理解这些问题并学会解决方法,而这些正是程序员实际编程生涯中至关重要的。

更多计算机宝库...