php专区

 首页 > php专区 > PHP进阶 > 算法 > 用递归实现的快速排序

用递归实现的快速排序

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

用递归实现的快速排序

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

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

#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 
#include 
using namespace std;
template 
int partition(T a[],int low,int high)
{
 T v=a[low];
 while(low=v) high--;
  a[low]=a[high];
  while(low
void QuickSort(T a[],int p,int q)
{
 stack st;
 int j;
 do{
      while(p												

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

用递归实现的快速排序
分享到:
收集一些top软件公司经典算法面试题
收集一些top软件公司经典算法面试题 微软 有一个整数数组,请求出两两之差绝对值最小的值,记住,只要得出最小值即可,不需要求出是哪两个数。 写一个函数,检查字符是否是整数,如果是,返回其整数值。(或者:怎样只用4行代码编写出一个从字符串到长整形的函数?) 给出一个函数来输出一个字符串的...
从1到N这N个数中1的出现了多少次?
从1到N这N个数中1的出现了多少次? 给定一个十进制整数N,求出从1到N的所有整数中出现"1"的个数。 例如:N=2,1,2出现了1个"1"。 N=12,1,2,3,4,5,6,7,8,9,10,11,12。出现了5个"1"。 最直接的方法就是从1开始遍历到N,将其中每一个数中含有"1"的个数加起来,就得到了问题的解。 publi...
  •         php迷,一个php技术的分享社区,专属您自己的技术摘抄本、收藏夹。
  • 在这里……