`
urey
  • 浏览: 25732 次
  • 性别: Icon_minigender_1
  • 来自: 广州
社区版块
存档分类
最新评论
  • carmark: 做什么都好,自己喜欢就好,我是做Unix以及C和perl相关的 ...
    混沌。
  • urey: toeo 写道我大学 也是信息与计算科学的我现在是做java  ...
    混沌。
  • toeo: 我大学 也是信息与计算科学的我现在是做java  弄web.要 ...
    混沌。

Quick Sort

J# 
阅读更多
//header in use
#include <stdio.h>
#include <tchar.h>

#include <stdlib.h>
#include <time.h>
#include <iostream>

using namespace std;
#define MAX 20

int _tmain(int argc, _TCHAR* argv[])
{
	int sortbox[MAX];
	long start, end;
	int Z = 0;
	void QuickSort(int *, int, int);
	srand(time(NULL));						//using rand() and time() to build ramdom number vector
	start = clock();
	while(Z != 1000){
		for(int i = 0; i != MAX; i++){
			sortbox[i] = rand() % 1000;
//			cout<<sortbox[i]<<' ';
		}
		QuickSort(sortbox, 0, MAX-1);
		Z++;
	}
	end = clock() - start;
	cout << endl;
	for(int i = 0; i != MAX; i++)
	{
		cout<<sortbox[i]<<' ';
	}
	cout << endl << end;
	return 0;
}

void QuickSort(int *box,int l, int r)				//
{
	int s = 0;
	int partition(int *, int, int );
	if(l<r){
		s = partition(box, l, r);
		QuickSort(box, l, s-1);
		QuickSort(box, s+1, r);
	}
	return;
}

int partition(int *box, int l, int r)
{
	int p = box[l];
	int i = l;
	int j = r + 1;
	void swap(int &, int &);							//referance! Use it carefully

	////////////////////////////////////////////////////////////////
	while(j>=i){
		do i++; while(i <= r && box[i] < p);
		do j--; while(j >=l && box[j] > p);
		swap(box[i], box[j]);
	}
	swap(box[i], box[j]);
	swap(box[l], box[j]);
	/*///////////////////////////////////////////////////////////////
	cout << endl;
	for(int i = 0; i != MAX; i++)
	{
		cout<<box[i]<<' ';
	}
	*/
	return j;
}

void swap(int &a, int &b)
{
	int tmp = a;
	a = b;
	b= tmp;
	return;
}

 

自己写的快速排序,随机生成数列循环一千次并记录时间,时间很不均匀,差别很大。本来希望实现选择前中后的中位数来进行但是出了问题,就没有写入了。

分享到:
评论

相关推荐

    quick sort

    Use QuickSort algorithm to sort the array that has n elements that are constructed by the random() function. Requirements: The template should be used for all kinds of data type, such as: integer, ...

    sort_exp.rar_quick sort_桶排序

    快速排序(Quick Sort)是由C.A.R. Hoare在1960年提出的,它是一种非常高效的排序算法,其基本思想是分治法。快速排序的基本步骤如下: 1. **选择枢轴元素**:在待排序的数组中选取一个元素作为枢轴,通常选择第一...

    Quick Sort in the worst case

    快速排序(Quick Sort)是一种高效的排序算法,由C.A.R. Hoare在1960年提出。其基本思想是采用分治法(Divide and Conquer),通过一趟排序将待排记录分割成独立的两部分,其中一部分的所有记录都比另一部分的所有...

    Quick sort Analysis.zip

    在这个名为"Quick sort Analysis.zip"的压缩包中,重点是分析快速排序的确定性与随机化实现。确定性快速排序通常是指每次选取固定的基准元素,如选择第一个或最后一个元素,这样对于相同的输入,排序过程完全可预测...

    PHP排序算法之快速排序(Quick Sort)及其优化算法详解

    快速排序(Quick Sort)是一种高效的排序算法,由C. A. R. Hoare在1960年提出。它采用分治法(Divide and Conquer)的策略来把一个序列分为较小和较大的两个子序列,然后递归地排序两个子序列。快速排序在实现时,...

    快速排序C实现 quick sort

    数据结构,排序算法,快速排序算法的C语言实现, quick sort C qsort.c an c implementation of quick sort

    quick sort算法图解

    快速排序算法(Quick Sort)是一种高效的排序算法,由计算机科学家托尼·霍尔(Tony Hoare)在1960年提出。它的基本思想是分治法(Divide and Conquer),通过一个基准值(pivot)将数组分为两部分,其中一部分的...

    python编写 快速排序 Quick Sort

    python编写 快速排序 Quick Sort

    C#,单向链表(Simply Linked List)快速排序(Quick Sort)算法与源代码

    各种数据结构、算法及实用的C#源代码.C#,单向链表(Simply Linked List)快速排序(Quick Sort)算法与源代码.单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部...

    C#,双向链表(Doubly Linked List)快速排序(Quick Sort)算法与源代码

    C#,双向链表(Doubly Linked List)快速排序(Quick Sort)算法与源代码。双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始...

    以 Quick Sort 算法将 ListBox 内容排序的范例(3k)

    快速排序(Quick Sort)是一种高效的排序算法,由C.A.R. Hoare在1960年提出。它的基本思想是采用分治法(Divide and Conquer),将一个大问题分解为两个或多个相同或相似的子问题,直到最后子问题可以简单的直接求解...

    python 一行代码实现的快速排序 quick sort

    python 一行代码实现的快速排序 quick sort

    快速排序(Quick Sort)

    ### 快速排序(Quick Sort) #### 算法原理 快速排序是一种高效的排序算法,其基本思想是采用分治法(divide and conquer)来解决问题。对于待排序的数组A[0]...A[N-1],快速排序通过选择一个基准元素(pivot),通常...

    快速排序(Quick Sort)源码及运行示例

    快速排序(Quick Sort)源码及运行示例

    快速排序(Quick Sort)作者原版论文PDF

    快速排序(Quick Sort)作者原版论文,快速排序的作者C.A.R Hoare 发表的原著论文。

    算法分析与设计教学课件:Chapter 7 Quick Sort.pptx

    算法分析与设计教学课件:Chapter 7 Quick Sort.pptx

    Quick Sort (C++)

    快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治法(Divide and Conquer)。在这个C++实现的快速排序中,我们将深入理解其原理、步骤以及如何用C++语言进行编码。...

    slides for merge and quick sort

    private static void sort(Comparable[] a, Comparable[] aux, int l, int r) { if (r ) return; int m = l + (r - l) / 2; sort(a, aux, l, m); // 排序左半部分 sort(a, aux, m, r); // 排序右半部分 ...

    基于python的排序算法-快速排序Quick Sort

    return quick_sort(left) + middle + quick_sort(right) # 示例 arr = [3, 6, 8, 10, 1, 2, 1] print(quick_sort(arr)) # 输出: [1, 1, 2, 3, 6, 8, 10] ``` 6. **时间复杂度与空间复杂度**: - **时间复杂度**...

Global site tag (gtag.js) - Google Analytics