• 欢迎浏览“String me = Creater\忠实的资深Linux玩家;”,请文明浏览,理性发言,有侵犯你的权益请邮件我(creater@vip.qq.com).
  • 把任何的失败都当作一次尝试,不要自卑;把所有的成功都想成是一种幸运,不要自傲。
  •    6年前 (2013-04-10)  算法/数据结构 |   1 条评论  23 
    文章评分 0 次,平均分 0.0

    排序是很多笔试面试常考的算法,值得加强学习。
    快排1.

    把数组第一个元素作为区分标准,存入临时变量tmp。 现在数组头部空出一个位。

    从右到左扫描到小于标准的数,放入该空位。 现在数组后半部分空出一个位

    从左到右扫描到大于标准的数,放入右边的空位, 现在数组左半部分有一空位

    。。。。

    当left == right时,则将tmp作为标准的数组,划分成两个区间爱你,左边的小于标准,右边的大于等于标准

    再递归该两个子区间

    void Qsort(int *a, int begin, int end) {
    	if(begin >= end)
    		return;
    	int left = begin;
    	int right = end;
    	int tmp = a[left];
    	while(left < right) {
    		while(right > left) {
    			if(a[right] >= tmp)
    				right --;
    			else
    				break;
    		}
    		if(right != left) {
    			a[left] = a[right];
    		}
    
    		while(left<right) {
    			if(a[left] < tmp)
    				left++;
    			else
    				break;
    		}
    		if(left != right) {
    			a[right] = a[left];
    		}
    	}
    	a[left] = tmp;
    	Qsort(a, begin, left -1);
    	Qsort(a, left+1, end);
    
    }

    快排2:把数组尾部元素作为标准,小于该标准的数依次从头交换,最后得到小于该标准的数都交换到数组头部。
    最后把这个标准与前边被判断出小于标准的序列的尾部。再递归该两个子区间

    void vswap(int &a, int &b){
    	int temp = a;
    	a = b;
    	b = temp;
    }
    void QSort(int a[], int begin, int end) {
    	if(begin >= end)
    		return;
    	int i,j;
    	int tmp = a[end];
    	int next = begin;
    	for(i = begin; i< end; i++) {
    		if(a[i] < tmp){
    			vswap(a[i], a[next++]);
    		}
    	}
    	vswap(a[next], a[end]);
    	QSort(a, begin, next-1);
    	QSort(a, next+1, end);
    }
     

    除特别注明外,本站所有文章均为String me = "Creater\忠实的资深Linux玩家";原创,转载请注明出处来自http://unix8.net/home.php/517.html

    关于

    发表评论

    暂无评论

    切换注册

    登录

    忘记密码 ?

    切换登录

    注册

    扫一扫二维码分享