网站开发经验与教训范文,深圳罗湖建网站,励志网站织梦源码,淮北论坛招聘希尔排序 优化版的插入排序#xff0c;优化的地方就是步长#xff08;增量#xff09;增大了#xff0c;原来的插入排序的步长#xff08;增量#xff09;是1#xff0c;而希尔排序的步长#xff08;增量#xff09;可以很大#xff0c;然后逐渐减小直到1形成插入排…希尔排序 优化版的插入排序优化的地方就是步长增量增大了原来的插入排序的步长增量是1而希尔排序的步长增量可以很大然后逐渐减小直到1形成插入排序
也叫减小增量排序
若不了解可看之前发布的希尔排序
void shellSort1(int arr[]int length){for(int iinterval;iarr.length;iinterval){int targetarr[i];int ji-interval;while(targetarr[j]){arr[jinertval]arr[j];j-interval;}arr[jinterval]target;}
}
个人感觉shellSort2更复杂一些。
void shellSort2(int arr[]int length){int h4;while(h1){for(int ih;ilength;i){for(int ji;jharr[j]arr[j-h];j-h){int temparr[j];arr[j]arr[j-h];arr[j-h]temp;}}h/2;}
}shellSort1的增量为length/2,不断取半
个人感觉shellSort1更好用shellSort2复杂一些shellSort更复杂。
经典的希尔序列1413.....,3*n1
void shellSort3(int arr[]int length){int h1;int tlength/3;while(ht)h3*h1;//让步长增量在length左右//shellSort2的步长给锁死成4了不过挺好用while(h1){for(int ih;ilength;i){for(int ji;jharr[j]arr[j-h];j-h){int temparr[j];arr[j]arr[j-h];arr[j-h]temp;}}h/3;}
} 快速排序 冒泡排序的优化版本核心思想使用轴每一轮左右递归后把轴放到中间使得轴的左边都比轴小轴的右边东渡比轴大当所有的递归都结束了就自然排序好了
pivot:轴(主元)一般选第一个元素
需要用到双指针一个左指针一个右指针
左指针找比轴(主元)大的右指针找比轴(主元)小的
然后二者值交换
void quickSort(int arr[],int left,int right){if(leftright)return;int ileft;//左指针int jright;//右指针int pivotarr[i];//该整体第一个元素并将主元提取出来while(ij){while(ijarr[j]pivot)j--;//找右边第一个小于pivot的值arr[i]arr[j];//然后把小于pivot的值给主元所在位置while(ijarr[i]pivot)i;//找左边第一个大于pivot的值arr[j]arr[i];将该值赋给第一个小于pivot的值//保留一个空位即原来主元空出来的位置可用于值的交换//左指针每找到一个大于pivot的值就停下右指针每找到一个小于pivot的值就停下然后二者互换// while(ijarr[i]pivot)循环条件添加ij是因为在while(ij)这个大循环中仍有两个while嵌套第一个while结束后,第二个while会继续执行i和j的位置就彼此越界了}arr[i]pivot;quickSort(arr,left,i-1);quickSort(arr,i1,right);}第二种写法void swap(int arr[],int i,int j){//换值函数int temparr[i];arr[i]arr[j];arr[j]temp;}
void quickSort2(int arr[],int left[],int right){//另一种快速排序的样例if(leftright)return;int pivotarr[left];int ileft1;//这里有两个指针int jleft1;while(jright){//每轮循环j都向右移一位if(arr[j]pivot){//如果j指向的值小于pivotswap(arr,i,j);//则交换i和j的值i;//每次将小于pivot的值移到左边i右移一位i就用于等待交换的位置每次j找到小于pivot的值都与i位置上的数交换}j;//j用于寻找小于pivot的值}swap(arr,left,i-1);//while循环结束后i最后1了所以i-1为最后一个小于pivot的值的位置因此将主元left上的值与i-1的值交换quickSort2(arr,left,i-2);//主元左边quickSort2(arr,i,right);//主元右边
}
