算法思想（二）——排序基础
写在前面：
视频：慕课网-学习算法思想，修炼编程内功
代码：Play-with-Algorithms/tree/master/02-Sorting-Basic/Course
使用rand 生成随机数，上限是rangeR，下线是rangeLarr[i]=rand()%(rangeR-rangeL+1)+rangeL;
SortTestHelper.h
//生成有n个元素的随机数组，每个元素的随机范围为[rangel，rangeR]int* generateRamdomArray(int n,int rangeL,int rangeR){assert(rangeL<=rangeR); int *arr = new int[n]; srand(time(NULL)); for(int i=0;i<n;i++)arr[i]=rand()%(rangeR-rangeL+1)+rangeL; return arr;} 12345678910
选择排序
SelectionSort.h
void selectionSort(int arr[],int n) {for(int i=0;i<n;i++){//寻找[i，n）区间里的最小值int minIndex=i;for(int j=i+1;j<n;j++)if (arr[j]<arr[minIndex])//此处比较可以定义为函数，例如less（），由用户定义大小比较规则{minIndex=j;}swap(arr[i],arr[minIndex]);} } 1234567891011121314 为什么要选择o（n2）的排序算法？（n方）
基础；
编码简单，易于实现，是一些简单情景的首选；
在一些特殊情况下，简单的排序算法更有效；
简单的排序算法思想衍生出复杂的排序算法；
作为子过程，改进更复杂的排序算法
template<typename T> void selectionSort(T arr[],int n) {//... } 12345 衡量算法性能
看算法在特定的数据集上的执行时间
SortTestHelper.h
//测试sort执行的正确性template<typename T>bool isSorted(T arr[],int n){ for(int i=0;i<n-1;i++) if(arr[i]>arr[i+1]) return false; return true;} //测试执行效率template<typename T>void testSort(string sortName,void(*sort)(T[],int), T arr[],int n)//参数 1 排序算法的名字 2 传入排序算法这个函数本身，即要传入一个函数指针。这样写：void(*sort)(T[],int) 3 测试用例数组 4 数组的个数{ clock_t startTime = clock(); sort(arr,n); clock_t endTime = clock(); assert( isSorted(arr,n));//assert 失败了，程序自动中断 //CLOCKS_PER_SEC 标准库中定义的宏，表示每秒钟执行的时钟周期个数 cout<< sortName<< " : "<< double(endTime-startTime)/CLOCKS_PER_SEC<<" s"<<endl;//程序执行了多少秒 return ;}//拷贝一个int型的数组int* copyIntArray(int a[],int n){ int* arr =new int[n]; copy(a,a+n,arr); return arr;}
1234567891011121314151617181920212223242526272829303132 测试：main.c
int main() {int n= 10000;int *arr = SortTestHelper::generateRamdomArray(n,0,n);SortTestHelper::testSort("selctionSort",selectionSort,arr,n);delete[] arr;return 0; } 12345678
插入排序
InsertionSort.h
template<typename T> void insertionSort(T arr[],int n) { for(int i=1;i<n;i++)//从第二个元素开始考察 { for(int j=i ; j>0 && arr[j]<arr[j-1] ; j--) { swap(arr[j],arr[j-1]); } } } 1234567891011 比较两种算法的时间
main.c
int main() {int n= 10000;int *arr = SortTestHelper::generateRamdomArray(n,0,n);int *arr2=SortTestHelper::copyIntArray(arr,n); SortTestHelper::testSort("selectionSort",selectionSort,arr,n); SortTestHelper::testSort("insertionSort",insertionSort,arr2,n);delete[] arr;delete[] arr2;return 0; } 1234567891011121314 对于10000个int类型的数，为何插入排序比选择排序还要慢？因为插入排序中的swap交换操作非常耗时（swap中至少有三次赋值操作）
如何改进插入排序的算法？让其只交换一次？ 改进的插入排序
template<typename T> void insertionSort(T arr[],int n) { for(int i=1;i<n;i++)//从第二个元素开始考察 { //寻找元素arr[i]合适的插入位置 T e =arr[i]; int j;//j保存元素e应该插入的位置 for(j=i ; j>0 && arr[j-1]>e; j--) { arr[j]=arr[j-1]; } arr[j]=e; } } 123456789101112131415 测试时间：
插入排序时间少，插入排序可以提前中止内层循环（若数组已基本有序，提前中止内存循环会使效率非常高）
此图的数据集为10000个（0，10000）范围内的数组
若将数据集改为10000个（0,3）范围内的数组，即int n= 10000; int *arr = SortTestHelper::generateRamdomArray(n,0,3);
随机数范围为0到3之前，对于10000个数，会存在大量的重复的数，由于有这些重复的数，整个数组的有序性要比之前的数据集强很多
再次运行
可见插入排序的效率提升的更高
方法：先生成一个完全有序的随机数组，然后再随机挑选几对元素进行交换，这样得到的数组近乎有序
SortTestHelper.h
int* generateNearlyOrderArray(int n,int swapTimes){ int *arr = new int[n]; for(int i=0;i<n;i++) arr[i]=i; srand(time(NULL)); for(int i=0;i<swapTimes;i++) { int posx =rand()%n; int posy =rand()%n; swap(arr[posx],arr[posy]); } return arr;} 123456789101112131415
测试：
int main() { int n= 100000;int *arr = SortTestHelper::generateNearlyOrderArray(n,100);int *arr2=SortTestHelper::copyIntArray(arr,n); SortTestHelper::testSort("selectionSort",selectionSort,arr,n); SortTestHelper::testSort("insertionSort",insertionSort,arr2,n); delete[] arr;delete[] arr2;return 0; } 1234567891011121314
可见插入排序虽然是o（n2）的算法，但在有些情况下却非常有效。
// 感谢github @zhengquan45 提出, 可以对选择排序进行优化 // 在每一轮中, 可以同时找到当前未处理元素的最大值和最小值 template<typename T> void selectionSort(T arr[], int n){ int left = 0, right = n - 1; while(left < right){ int minIndex = left; int maxIndex = right; // 在每一轮查找时, 要保证arr[minIndex] <= arr[maxIndex] if(arr[minIndex] > arr[maxIndex]) swap(arr[minIndex], arr[maxIndex]); for(int i = left + 1 ; i < right; i ++) if(arr[i] < arr[minIndex]) minIndex = i; else if(arr[i] > arr[maxIndex]) maxIndex = i; swap(arr[left], arr[minIndex]); swap(arr[right], arr[maxIndex]); left ++; right --; } return; }
1234567891011121314151617181920212223242526272829 补充二：冒泡排序// 我们的第一版bubbleSort template<typename T> void bubbleSort( T arr[] , int n){ bool swapped; do{ swapped = false; for( int i = 1 ; i < n ; i ++ ) if( arr[i-1] > arr[i] ){ swap( arr[i-1] , arr[i] ); swapped = true; } // 优化, 每一趟Bubble Sort都将最大的元素放在了最后的位置 // 所以下一次排序, 最后的元素可以不再考虑 n --; }while(swapped); } // 我们的第二版bubbleSort,使用newn进行优化 template<typename T> void bubbleSort2( T arr[] , int n){ int newn; // 使用newn进行优化 do{ newn = 0; for( int i = 1 ; i < n ; i ++ ) if( arr[i-1] > arr[i] ){ swap( arr[i-1] , arr[i] ); // 记录最后一次的交换位置,在此之后的元素在下一轮扫描中均不考虑 newn = i; } n = newn; }while(newn > 0); }
1234567891011121314151617181920212223242526272829303132333435363738394041 补充三：希尔排序template<typename T> void shellSort(T arr[], int n){ // 计算 increment sequence: 1, 4, 13, 40, 121, 364, 1093... int h = 1; while( h < n/3 ) h = 3 * h + 1; while( h >= 1 ){ // h-sort the array for( int i = h ; i < n ; i ++ ){ // 对 arr[i], arr[i-h], arr[i-2*h], arr[i-3*h]... 使用插入排序 T e = arr[i]; int j; for( j = i ; j >= h && e < arr[j-h] ; j -= h ) arr[j] = arr[j-h]; arr[j] = e; } h /= 3; } }
12345678910111213141516171819202122232425相关知识
冒泡排序，选择排序，二分法查找，顺序查找
冒泡排序
数据挖掘算法中，预测类模型详解
java冒泡排序
java题：请使用任意一例排序算法,对int[] intArr={5,9,1,4,1,2,6,3,8,0,7}进行排序
思想状况分析报告
排序游戏：锻炼宝宝的观察技能
BF算法详解
腾讯多任务强化学习算法登上顶刊TPAMI
思想政治素质情况怎么写(思想政治素质怎么填)
网址: 算法思想（二）——排序基础 https://m.mcbbbk.com/newsview1052655.html
| 上一篇: 怎么买小猫，怎么买宠物猫 |
下一篇: 动物科学专业介绍及描述 .pdf |
