建设单位网站的重要性,wordpress多站点必备插件,室内设计官方网站,有那些网站可以做推广快速排序的思想大体来说比较简单#xff0c;就是从数组中挑选一个数字当做枢纽#xff0c;然后将比枢纽大的和比枢纽小的分别放在枢纽的两边#xff0c;再递归地对两边进行操作#xff0c;从而进行分治解决问题。平均情况下快速排序是复杂度为O(nlogn)O(nlogn)O(nlogn)就是从数组中挑选一个数字当做枢纽然后将比枢纽大的和比枢纽小的分别放在枢纽的两边再递归地对两边进行操作从而进行分治解决问题。平均情况下快速排序是复杂度为O(nlogn)O(nlogn)O(nlogn)可是有时候复杂度会退化为O(n2)O(n^2)O(n2)这与我们如何选择枢纽以及如何将数组进行划分有关。
总共有两种情况下复杂度会退化 数组大体有序这个时候如果我们枢纽选择的不够好那么数组的一边将会比较大一边将会比较小最严重的时候每次只能将规模减一则复杂度将会变成T(n)T(n−1)nT(n)T(n-1)nT(n)T(n−1)n即T(n)n2T(n)n^2T(n)n2。解决这个问题的方法就是合理的选择枢纽例如选择数组头部、尾部、中间三个数字的平均值这种方法就能有有效解决这个问题。我们一般将枢纽放在数组的头部只需要交换选择的枢纽和原本位于枢纽头部的元素即可这样做可以方便我们进行划分。 数组中有很多一模一样的数字这样同样会产生每次只能将规模减小很少的情况最坏的时候复杂度也将退化为O(n2)O(n^2)O(n2)。这种问题的产生我们无法通过有效的选择枢纽解决只能够通过划分的时候使得即使数组中的元素都等于枢纽我们仍旧能够将数组大概分成相等的两部分。
常见的有以下划分方法 从一边进行划分 大概的思想就是把第一个元素当做枢纽然后使用一个指针保存分界点指针的左边是小于枢纽的元素指针的右边是大于等于枢纽的元素必须有一边支持等于否则划分将会卡住。 将指针初始化在数组头部遍历后面的元素如果比枢纽小就将指针向后移动一位然后将该位置的元素和遍历到的元素交换。否则就继续向后遍历。这样做可以成功的原因是任何时刻指针后面的元素都是大于等于枢纽的元素通过交换就将小于枢纽的元素放在了指针之前从而完成划分。 实现代码 void QuickSort(T* a,int l,int r)
{if(r-l2) return;//从一边划分int indexl;T xa[l];for(int il1;ir;i){if(a[i]x)swap(a[index],a[i]);}swap(a[index],a[l]);QuickSort(a,l,index); QuickSort(a,index1,r);虽然这种方法实现起来比较简单但是他不能够解决出现大量重复元素复杂度提升的问题。
从两边进行划分 空穴法 我们先将枢纽元素取出数组然后用两个指针分别指向数组头部和数组尾部先从尾部找比枢纽元素小的元素找到以后放在数组头部因为将枢纽元素取出形成的空穴中此时指向数组尾部的指针所指向的元素被取走形成空穴再从头部找比枢纽大的元素找到以后再放在尾部形成的空穴中。如此反复直到两个指针相遇然后再将枢纽放在最后的这个空穴中完成划分。 实现代码 void QuickSort(T* a,int l,int r){if(r-l2) return;//空穴法int il,jr-1;T xa[l];while(ij){while(ij a[j]x) --j; a[i]a[j];while(ij a[i]x) i;a[j]a[i];}a[i]x;QuickSort(a,l,i); QuickSort(a,i1,r);}这中方法我们同样必须在一边允许等号因此也可能出现复杂度退化的问题 直接交换 当然我们也可以直接进行交换而不使用空穴一种简单的实现方法 void QuickSort(T* a,int l,int r)
{if(r-l2) return;int il1,jr-1;T xa[l];while(ij){while(ir a[i]x) i;while(jl a[j]x) --j;if(ij) swap(a[i],a[j]);}swap(a[l],a[j]);QuickSort(a,l,j);QuickSort(a,i,r);然而这种方法依旧不能够解决问题不会采用因此我们需要进行一些变形 实现代码 void QuickSort(T* a,int l,int r)
{if(r-l2) return;int il-1,jr;T pivot a[l];while(ij){do i; while(a[i] pivot);do --j; while(a[j] pivot);if(i j) swap(a[i],a[j]);}QuickSort(a,l,j1); QuickSort(a,j1,r);为什么这样做就可以解决重复元素的问题呢这里和上面方法最大的不同就在于我们在划分的时候没有使用等号。这样的话如果遇到和枢纽相等的元素的时候我们就移动然后越过这个位置。使用dododo while;while;while;结构就是为了能够跨越和枢纽相等的元素。如果整个数组都是相等的话虽然我们多进行一些交换但是有效地将数组划分成了差不多相等的两部分。 对于代码的理解很重要的一点就是将il−1il-1il−1。刚开始我觉得这一点没有很重要所以自己将其改为了ililil然后最后将枢纽元素放在中间。但是在测试的时候我发现对于有些数据会出错。仔细推敲数据以后发现il−1il-1il−1的意义不仅仅在于第一个do()whiledo() whiledo()while结构可以将枢纽元素计算进去更重要的是一个哨兵的作用。因为后面我们进行移动指针的时候并没有判断指针是否越界。对于右边的指针无论如何一定会停下来因为它的左边至少还有一个和枢纽元素相等的元素枢纽元素本身但是如果左边我们刚开始的时候跳过了枢纽元素那么如果在数组末尾的话就会越界。只有让左边刚开始为il−1il-1il−1那么指针至少会停在枢纽元素的位置。如果发生了交换的话那么指针也一定会停在交换时右边指针位置的前面。还有一点就是第12行区间分割为[l,j1) [j1,r)而不是[l,j),[j,r)因为后面这种做法有可能导致左边[l,j)的区间长度为0这样将会导致栈溢出。产生这种现象的原因主要是枢纽元素选择的不恰当对于选择第一个元素作为枢纽来讲j一定是小于r-1的因为第一次肯定会卡住所以不用担心j1等于r。如果枢纽选择的比较恰当就不会出现这种问题。
上面的这种做法没有将枢纽元素放在中间但是因为他不害怕重复元素所以不用担心问题的规模不减小而产生栈溢出。
通过划分解决了上面的问题以后我们就可以得到一个复杂度挺优秀的快速排序了。
实现代码
#include iostreamusing namespace std;typedef double T;T* CreatList(int n)
{printf(n); scanf(%d,n);T* ret new T[n];for(int i0;in;i){cinret[i];}return ret;
}void Init(T* a,int l,int r)
{int mid(lr)1;if(a[mid] a[l]) swap(a[mid],a[l]);if(a[mid] a[r-1]) swap(a[mid],a[r-1]);if(a[l] a[r-1]) swap(a[l],a[r-1]);return;
}void QuickSort(T* a,int l,int r)
{if(r-l2) return;Init(a,l,r);//将首部、尾部、中间三个数中的中值放在开头int il-1,jr;T pivot a[l];while(ij){do i; while(a[i] pivot);do --j; while(a[j] pivot);if(i j) swap(a[i],a[j]);}QuickSort(a,l,j1); QuickSort(a,j1,r);
}void Show(T* a,int n)
{for(int i0;in;i){couta[i] ;}coutendl;
}int main()
{int n;T* aCreatList(n);QuickSort(a,0,n);cout经过排序之后:endl;Show(a,n);delete[] a;return 0;
}
为了验证是否我们的确对算法的效率进行了提高我编写了测试程序单位为SSS环境为Ubuntu18.04Ubuntu18.04Ubuntu18.04
数据规模1e5乱序1e6乱序1e7乱序5e4重复5e4有序一侧划分取中值0.0211840.2552262.9136692.9649050.005573空穴法划分取中值0.0148650.1723061.9809303.1350600.002652两侧直接划分取中值0.0170330.1953182.2361710.0048140.002670两侧直接划分0.0162390.1895922.1781690.0047002.622307
为了减少运行时操作系统的影响每个数据规模运行我都运行十次然后取平均值。
虽然仍旧可能还有数据本身的影响但是我们也能够大概看出来一个大体的变化规律。当数据为乱序的时候空穴法是比较优秀的但是当出现重复元素时两侧直接划分的方法碾压前面两种方法。当数据大体是有序的时候如果我们选取枢纽直接选择第一个其时间复杂度也是可怕的。
因此综合考虑我们采用第三种方法是比较好的。
测试程序代码
#include iostream
#include ctime
#include cstdio
#include fstream
#include cstdlibusing namespace std;typedef double T;
typedef void (*FP)(T*,int,int); //定义函数指针数组类型void CreatData()
{int n10;FILE* filefopen(TestFile,w);fprintf(file,%d\n,n);int t;srand(t);for(int i0;in;i){trand();fprintf(file,%d ,rand()%10);}fclose(file);return ;
}T* CreatList(int n)
{//printf(n);//CreatData();ifstream in(TestFile);in n;T* ret new T[n];for(int i0;in;i){inret[i];}in.close();return ret;
}void Init(T* a,int l,int r)
{int mid(lr)1;if(a[mid] a[l]) swap(a[mid],a[l]);if(a[mid] a[r-1]) swap(a[mid],a[r-1]);if(a[l] a[r-1]) swap(a[l],a[r-1]);return;
}void QuickSort1(T* a,int l,int r)
{if(r-l2) return;Init(a,l,r);//将首部、尾部、中间三个数中的中值放在开头//从一边划分int indexl;T xa[l];for(int il1;ir;i){if(a[i]x)swap(a[index],a[i]);}swap(a[index],a[l]);QuickSort1(a,l,index); QuickSort1(a,index1,r);
}void QuickSort2(T* a,int l,int r)
{if(r-l2) return;Init(a,l,r);//将首部、尾部、中间三个数中的中值放在开头//空穴法int il,jr-1;T xa[l];while(ij){while(ij a[j]x) --j; a[i]a[j];while(ij a[i]x) i;a[j]a[i];}a[i]x;QuickSort2(a,l,i); QuickSort2(a,i1,r);
}void QuickSort3(T* a,int l,int r)
{if(r-l2) return;Init(a,l,r);//将首部、尾部、中间三个数中的中值放在开头int il-1,jr;T pivot a[l];while(ij){do i; while(a[i] pivot);do --j; while(a[j] pivot);if(i j) swap(a[i],a[j]);}QuickSort3(a,l,j1); QuickSort3(a,j1,r);
}void QuickSort4(T* a,int l,int r)
{if(r-l2) return;int il-1,jr;T pivot a[l];while(ij){do i; while(a[i] pivot);do --j; while(a[j] pivot);if(i j) swap(a[i],a[j]);}QuickSort4(a,l,j1); QuickSort4(a,j1,r);
}void Show(T* a,int n)
{for(int i0;in;i){couta[i] ;}coutendl;
}void Test(FP fp[])
{for(int i0;i4;i){clock_t S,E;int Time 10;double sum0;for(int j0;jTime;j){int n;T* aCreatList(n);Sclock();fp[i](a,0,n);Eclock();sum(double)(E-S)/CLOCKS_PER_SEC;//cout经过排序之后:endl;//Show(a,n);delete[] a;}printf(QuickSort%ds times%f\n,i1,sum/Time);}
}int main()
{FP fp[4] {QuickSort1,QuickSort2,QuickSort3,QuickSort4};Test(fp);return 0;
}
