求解排序算法

Question

使用双向链表 时间复杂度不能超过nlogn,最坏不能退化为n^2 空间复杂度O(1).求思路

Answer 1

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
//定义类型 所有的排序例子中都是用的int作为data
typedef int elemType;     
//返回值
#define RET_SUCCESS   ( 1  ) 
#define RET_FAILED   ( 0  )  
//定义链表的长度
#define  LIST_MAX_SIZE      (10)
//定义链表申请内存不够时报错信息
#define NO_MEMORY   printf("Error! Not enough memory!/n");exit(1)
//双向链表结构体定义
typedef struct tagDuNode_t
{
 elemType data;     
 struct tagDuNode_t * pstNext; 
 struct tagDuNode_t * pstPrior;
}duNode_t;
//初始化双向链表
int initDuList(duNode_t ** pstHead)
{
 int iRet = RET_SUCCESS;
 int iCir = 0;
 duNode_t * pstTmp1 = NULL;
 duNode_t * pstTmp2 = NULL;
 
 //初始化头节点
 * pstHead = (duNode_t *)malloc(sizeof(duNode_t));
 (* pstHead)->pstPrior = NULL;
 (* pstHead)->pstNext = NULL;
 if ( !pstHead )
 {
  NO_MEMORY;
 }
 pstTmp1 = * pstHead;
 //链表初始化
 srand( time(NULL) );//随机数
    for( iCir = 0; iCir < LIST_MAX_SIZE; iCir++ )
 {
  pstTmp2 = (duNode_t *)malloc(sizeof(duNode_t));
  if ( !pstTmp2 )
  {
   NO_MEMORY;
  }
  //赋初值
  pstTmp2->data = rand() % LIST_MAX_SIZE;
  pstTmp2->pstNext = NULL;
  pstTmp1->pstNext = pstTmp2;
  pstTmp2->pstPrior = pstTmp1;
  pstTmp1 = pstTmp2;
 } 
 return iRet;
}
// 打印链表 链表的data元素是可打印的整形    
int showDuList(duNode_t * pstHead)
{
 int iRet = RET_SUCCESS;
 duNode_t * pstTmp = pstHead->pstNext;
 if ( NULL == pstHead )
 {
  printf("链表的头节点是空/n");
  iRet = RET_FAILED;
 }
 else
 {
  while ( pstTmp )
  {
   printf("%d ", pstTmp->data);
   pstTmp = pstTmp->pstNext;
  }
  printf("/n");
 }
 return iRet;
}
/* 删除包括头节点在内的所有的节点. 07/04/28  */
int destroyList(duNode_t * pstHead)
{
 duNode_t * pstTmp = NULL;   /* Temp pointer for circle  */
 int iRet = RET_SUCCESS;
 if ( !pstHead )
 {
  printf("Error! pstHead is null/n");
  iRet = RET_FAILED;
 }
 else
 {
  while ( pstHead )  /* Free  nodes      */
  {
   pstTmp = pstHead;
   pstHead = pstHead->pstNext;
   free(pstTmp);
  }
  pstHead = NULL;
 }
 return iRet;
}/* End of destroyList----------------------------------------------*/
/*
 一趟快速排序的具体做法是：附设两个指针low和high(即第一个和最后一个指针),
 他们的初值分别为low和high设枢轴(一般为low的值pivot)记录的关键字
 (即本例子中的整形data)为pivot，则首先从high所指位置
 起向前搜索到第一个关键字小于pivot的记录和枢轴记录交换，然后从low所指位置起
 向后搜索，找到第一个关键字大于pivot的记录和枢轴记录相互交换，重复这两步直
 至low = high为止。
*/
duNode_t * partion(duNode_t * pstHead, duNode_t * pstLow, duNode_t * pstHigh)
{
 elemType iTmp = 0;
 elemType pivot = 0;
 if ( !pstHead )
 {
  printf("错误，头节点为空！/n");
  exit(1);
 }
 if ( !pstHead->pstNext )
 {
  return pstHead->pstNext;//就一个元素
 } 
 pivot = pstLow->data;
 while ( pstLow != pstHigh )
 {
  //从后面往前换
  while ( pstLow != pstHigh && pstHigh->data >= pivot )
  {
   pstHigh = pstHigh->pstPrior;
  }
  //交换high low
  iTmp = pstLow->data;
  pstLow->data = pstHigh->data;
  pstHigh->data = iTmp;
  //从前往后换
  while ( pstLow != pstHigh && pstLow->data <= pivot )
  {
   pstLow = pstLow->pstNext;
  }
  //交换high low
  iTmp = pstLow->data;
  pstLow->data = pstHigh->data;
  pstHigh->data = iTmp;
 }
 return pstLow;
}
//快排
void quick_sort(duNode_t * pstHead, duNode_t * pstLow, duNode_t * pstHigh)
{
 duNode_t * pstTmp = NULL;
 pstTmp = partion(pstHead, pstLow, pstHigh);
 if ( pstLow != pstTmp )
 {
  quick_sort(pstHead, pstLow, pstTmp->pstPrior);
 }
 if ( pstHigh != pstTmp )
 {
  quick_sort(pstHead, pstTmp->pstNext, pstHigh);
 }
 
}
void main()
{
 duNode_t * pstHead = NULL;
 duNode_t * pstHigh = NULL;
 duNode_t * pstTmp = NULL;
 initDuList(&pstHead);   //初始化
 printf("Before sorting:/n");
 showDuList(pstHead);   //打印
 pstTmp = pstHead->pstNext;
 while ( pstTmp->pstNext )
 {
  pstTmp = pstTmp->pstNext;
 }
 pstHigh = pstTmp;//找到最后一个节点的指针用于快排时
 quick_sort(pstHead, pstHead->pstNext, pstHigh);//快排序
 printf("After sorting:/n");
 showDuList(pstHead);
 destroyList(pstHead);
 pstHead = NULL;
}