//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;
}
自己写的快速排序,随机生成数列循环一千次并记录时间,时间很不均匀,差别很大。本来希望实现选择前中后的中位数来进行但是出了问题,就没有写入了。
分享到:
相关推荐
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, ...
快速排序(Quick Sort)是由C.A.R. Hoare在1960年提出的,它是一种非常高效的排序算法,其基本思想是分治法。快速排序的基本步骤如下: 1. **选择枢轴元素**:在待排序的数组中选取一个元素作为枢轴,通常选择第一...
快速排序(Quick Sort)是一种高效的排序算法,由C.A.R. Hoare在1960年提出。其基本思想是采用分治法(Divide and Conquer),通过一趟排序将待排记录分割成独立的两部分,其中一部分的所有记录都比另一部分的所有...
在这个名为"Quick sort Analysis.zip"的压缩包中,重点是分析快速排序的确定性与随机化实现。确定性快速排序通常是指每次选取固定的基准元素,如选择第一个或最后一个元素,这样对于相同的输入,排序过程完全可预测...
快速排序(Quick Sort)是一种高效的排序算法,由C. A. R. Hoare在1960年提出。它采用分治法(Divide and Conquer)的策略来把一个序列分为较小和较大的两个子序列,然后递归地排序两个子序列。快速排序在实现时,...
数据结构,排序算法,快速排序算法的C语言实现, quick sort C qsort.c an c implementation of quick sort
快速排序算法(Quick Sort)是一种高效的排序算法,由计算机科学家托尼·霍尔(Tony Hoare)在1960年提出。它的基本思想是分治法(Divide and Conquer),通过一个基准值(pivot)将数组分为两部分,其中一部分的...
python编写 快速排序 Quick Sort
各种数据结构、算法及实用的C#源代码.C#,单向链表(Simply Linked List)快速排序(Quick Sort)算法与源代码.单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部...
C#,双向链表(Doubly Linked List)快速排序(Quick Sort)算法与源代码。双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始...
快速排序(Quick Sort)是一种高效的排序算法,由C.A.R. Hoare在1960年提出。它的基本思想是采用分治法(Divide and Conquer),将一个大问题分解为两个或多个相同或相似的子问题,直到最后子问题可以简单的直接求解...
python 一行代码实现的快速排序 quick sort
### 快速排序(Quick Sort) #### 算法原理 快速排序是一种高效的排序算法,其基本思想是采用分治法(divide and conquer)来解决问题。对于待排序的数组A[0]...A[N-1],快速排序通过选择一个基准元素(pivot),通常...
快速排序(Quick Sort)源码及运行示例
快速排序(Quick Sort)作者原版论文,快速排序的作者C.A.R Hoare 发表的原著论文。
算法分析与设计教学课件:Chapter 7 Quick Sort.pptx
快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治法(Divide and Conquer)。在这个C++实现的快速排序中,我们将深入理解其原理、步骤以及如何用C++语言进行编码。...
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); // 排序右半部分 ...
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. **时间复杂度与空间复杂度**: - **时间复杂度**...