4
回答
麻烦高手帮忙看个问题,关于快速排序法
注册华为云得mate10,2.9折抢先购!>>>   
#include <stdio.h>
  2 
  3 static void swap(int *a, int *b)
  4 {
  5 |   int tmp = *a;
  6 |   *a = *b;
  7 |   *b =tmp;
  8 }
  9 
 10 static int findPivot(int *a, int left, int right)
 11 {
 12 |   int center = (int)(left+right)/2;
 13 
 14 |   if(a[left]>a[right])
 15 |   |   swap(&a[left], &a[right]);
 16 |   if(a[center]>a[right])
 17 |   |   swap(&a[center], &a[right]);
 18 |   if(a[center]<a[left])
 19 |   |   swap(&a[center], &a[left]);
 20 
 21 |   swap(&a[center], &a[right-1]);
 22 
 23 |   return a[right-1];
 24 }
 25 
 26 void quickSort(int *a, int left, int right)
 27 {
 28 |   if(left<right)
 29 |   {
 30 |   |   int i=left,j=right-1;
 31 
 32 |   |   int pivot = findPivot(a, left, right);
 33 |   |   for(;;)
 34 |   |   {
 35 
 36 |   |   |   while(a[++i]<pivot);
 37 |   |   |   while(a[--j]>pivot);
 38 |   |   |   if(i<j)
 39 |   |   |   |   swap(&a[i], &a[j]);
 40 |   |   |   else
 41 |   |   |   |   break;
 42 |   |   }
 43 |   |   
 44 |   |   swap(&a[i], &a[right-1]);
 45 
 46 |   |   quickSort(a, left, i-1);
 47 |   |   quickSort(a, i+1, right);
 48 
 49 |   }
 50 
 51 }
 52 
 53 int main(int argc, char** argv)
 54 {
 55 |   int a[] = {23,545,568,8985,4,1,567,0,8976,35423,1};
 56 |   printf("%s\n", "Before quick Sort");
 57 |   int i = 0;
 58 |   for(i=0;i<sizeof(a)/sizeof(int);i++)
 59 |   |   printf("%d\t", a[i]);
 60 
 61 |   printf("\n");
 62 
 63 |   quickSort(a, 0, sizeof(a)/sizeof(int)-1);
 64 |   
 65 |   printf("%s\n", "After quick Sort"); for(i=0;i<sizeof(a)/sizeof(int);i++)
 68 |   |   printf("%d\t", a[i]);
 69 
 70 |   printf("\n");
 71 |   return 0;
 72 }


这是我无聊时写的一个快排,但是排序结果始终不对,仿照<数据结构与算法分析--C++描述(第三版)>这本书的例子写的。

麻烦高手帮我查查看到底哪步骤除了问题,非常感谢!!!

<无标签>
举报
xinzaibing
发帖于6年前 4回/109阅
共有4个答案 最后回答: 6年前
FT。你竟然用递归!!!!!本来想帮你改的。 帮你编辑了代码,跑到quick_sort函数时才发现。我马上写个和你这个比较贴近的算法。你自己对比一下。

给楼主个建议,用一个7个元素的集合单步调试,先用人脑把过程做出来,再用机器,看看哪一步不同,再把原因找出来。

P.S. 我当年调了大约7个小时

--- 共有 2 条评论 ---
xinzaibing按照你给的方法终于解决了...谢谢啦! 6年前 回复
xinzaibing是啊,递归的调试太egg pain了... 谢谢指导! 6年前 回复

下面是粗糙版的排序,入口和你的入口一样。记得对堆栈空间进行调整。正常这里push, pop是用汇编的,直接使用系统的堆栈。

int push_buf[1024];
int push_sp = 0;
#define PUSH(a) do{push_buf[push_sp++] = a;}while(0)
#define POP(a) do {a = push_buf[--push_sp];}while (0)
#define EMPTY() (push_sp == 0)

void QuickSort(int data[], int left, int right)
{
        register int temp = data[left];
        int p = left;
        int i = left, j = right;
 		PUSH(left);
 		PUSH(right);
 		while (!EMPTY()){
		    while (i <= j){
		            while (data[j] >= temp && j >= p ){
		                    j--;
		            }        
		            if(j >= p){
		                    data[p] = data[j];
		                    p = j;
		            }
		            while (data[i] <= temp && i <= p){
		                i++;
		            }        
		            if (i <= p){
	                    data[p] = data[i];
	                    p = i;
		            }
		    }
		    data[p] = temp;
		    if(p-left > 1){
		    	PUSH(left);
		    	PUSH(p-1);
		    }
		    if(right - p > 1){
		    	PUSH(p+1);
		    	PUSH(right);
		    }
		    POP(right);
		    POP(left);
		    j = right;
		    i = left;
		    p = left;
		    temp = data[left];
		}
}

--- 共有 2 条评论 ---
xinzaibing你这个貌似是非递归实现... 没见过非递归快排,要好好研究下...谢谢啦!^_^ 6年前 回复
xinzaibing谢谢野鬼!!还在上班,晚上回去再调调! 6年前 回复
回楼主,需要注意一下,有些算法分析,比如算空间复杂度就是胡扯淡。有些空间复杂度确实增加的,但是没有递归,实际空间使用量比后者还小。而一些算法分析却来句系统会处理掉。另外,递归非常耗时间,你如果写过汇编,跟踪过cycle就知道了。上面的版本不适合多线程操作。多线程操作存在切割并用相同函数实现的,但不叫递归。是任务分解和clone。
--- 共有 1 条评论 ---
xinzaibing请教另外个问题,对于整数排序,使用快排的递归实现来进行排序,大约多大数据量会有可能造成栈溢出的问题..? 6年前 回复
顶部