邹城建设银行网站,网站建设与管理好处,大众点评网站模板,网站建设经费的函快速排序算法最早是由图灵奖获得者Tony Hoare设计出来的,他在形式化方法理论以 及ALGOL.60编程语言的发明中都有卓越的贡献,是20世纪最伟大的计算机科学家之—。 而这快速排序算法只是他众多贡献中的—个小发明而已。
快速排序#xff08;Quick Sort#xff09;的基本算法思…快速排序算法最早是由图灵奖获得者Tony Hoare设计出来的,他在形式化方法理论以 及ALGOL.60编程语言的发明中都有卓越的贡献,是20世纪最伟大的计算机科学家之—。 而这快速排序算法只是他众多贡献中的—个小发明而已。
快速排序Quick Sort的基本算法思想是通过一趟排序将待排记录分割成独立的两部分其中一部分记录的关键字均比另一部分记录的关键字小则可以分别对这两部分记录继续进行排序以达到整个序列有序的目的。
接下来我们一起来认识一下快排。
霍尔版本
快排共有三种实现方法最初的一代就是创始人霍尔的版本 霍尔版本是数组的数选定数组第一个位置keyi然后从数组的最右边rightn-1往前一个个找到比keyi位置小的数接下来从最左边left0开始找到第一个比Keyi位置大的数然后交换刚才找到的右边小的数和左边大的数接下来继续从右边找小从左边找大等到right和left相遇时停下此时再交换keyi和left(right)位置的数那么比这个key小的数都在key的左边比Key大的数都在key的右边再递归0到keyi-1keyi1到n-1位置的数如此下来就可以得到有序的数据。
接下来我们开始实现
int PartSort1(int* a, int left, int right)
{int keyi left;while (left right)//left和right相遇时循环停下{while (leftrighta[right] a[keyi])//找小{right--;//right没找到小right--往下走}while (left right a[left] a[keyi])//找大{left;//left没找到大left往下走}Swap(a[left], a[right]);//将找到的小的和大的交换位置}Swap(a[left], a[keyi]);//最后left和keyi交换位置return left;
} 这是一趟keyi的找大找小过程一个过程只能确定一个数的位置我们还需要继续递归keyi的左边和keyi的右边。
int keyi PartSort1(a, begin, end); QuickSort(a, begin, keyi - 1); QuickSort(a, keyi1, end);
但是什么时候停止呢当区间只有一个数的时候就需要停止即beginend时候return。但是还可能存在只剩区间【00】时此时keyi1,begin0,keyi-10;keyi12,end0,发生不存在区间所以就会停止。 void QuickSort(int* a, int begin,int end)
{if (begin end)//{return;}int keyi PartSort1(a, begin, end);//每次可以确定一个keyi位置保证不再变动QuickSort(a, begin, keyi - 1);QuickSort(a, keyi1, end);
}
上述partsort1版本就是霍尔版本的快排。
挖坑法
第二个实现快排的方法是挖坑法 挖坑法呢其实就是也是从a[0]开始记keya[0]在最开始处即a[0]处定义一个hole(坑),从右边开始找比key小的值找到了把a[right]处赋给上一个hole,使right现在的位置为新的hole再从左边left处找到比key大的值把a[left]的值赋给上一个hole,使left现在的位置为新的hole,下面我们一起实现。
int PartSort2(int* a, int left, int right)
{int key a[left];int hole left;while (left right){while (leftright a[right]key){right--;}a[hole] a[right];hole right;while (leftright a[left]key){left;}a[hole] a[left];hole left;}a[hole] key;//相遇后把最后一个hole位置的值给key;return hole;
}
最后返回hole的位置接下来就和上面一样QuickSort直接调用PastSort2,然后递归就可以啦。
前后指针法
第三种实现快排的方法是 前后指针法虽然说是前后指针其实并不是使用指针而是两个下标一前一后走。所谓前后指针法就是定义两个下标cur和pre,pre初始为Left,cur是left1的位置记录keyileft的位置的值cur从当前位置依次往后找比a[keyi]小的值如果比a[keyi]大或者等于cur就往后走如果小于a[lkeyi]的值则pre要然后交换cur和pre的位置直到cur走到末尾。最后在交换pre和keyi位置的数值返回keyi位置就可以了。
下面我们实现
int PartSort3(int* a, int left, int right)
{int pre left;int cur left 1;int keyi left;while (cur right){if (a[cur] a[keyi])//找小{cur;//没找到就继续往下走}else{pre;Swap(a[pre], a[cur]);//找到了就和pre位置交换cur;}}Swap(a[keyi], a[pre]);keyi pre;return keyi;
}
上述写法还可以优化我们想如果前几个cur位置都比a[keyi]小的话也就是先pre再交换pre和cur位置再cur,可是本来最初cur就比pre提前一个位置如果一组数据前几个数都是a[cur]a[keyi]的话就一直是相同的cur位置和pre位置交换。我们可以写成
while (curright)
{if (a[cur] a[keyi] pre ! cur)//只有在pre!cur的情况下再交换{Swap(a[cur], a[pre]);}cur;
}
这样就可以减少不必要无意义的交换了。
以上就是三种快排的实现方法个人而言觉得第三种前后指针法更简便更容易实现。当然这三种方法并没有本质区别和性能区别掌握哪种都一样都能掌握当然是最好的。 快速排序的特性总结 1. 快速排序整体的综合性能和使用场景都是比较好的所以才敢叫 快速 排序 2. 时间复杂度 O(N*logN) 3.空间复杂度 O(logN) 源代码 #includestdio.h
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}int PartSort1(int* a, int left, int right)//霍尔
{int keyi left;while (left right){while (leftrighta[right] a[keyi]){right--;}while (left right a[left] a[keyi]){left;}Swap(a[left], a[right]);}Swap(a[left], a[keyi]);return left;
}
int PartSort2(int* a, int left, int right)//挖坑
{int key a[left];int hole left;while (left right){while (leftright a[right]key){right--;}a[hole] a[right];hole right;while (leftright a[left]key){left;}a[hole] a[left];hole left;}a[hole] key;return hole;
}
int PartSort3(int* a, int left, int right)//前后指针
{int pre left;int cur left 1;int keyi left;/*while (cur right){if (a[cur] a[keyi]){cur;}else{pre;Swap(a[pre], a[cur]);cur;}}*/while (cur right){if (a[cur] a[keyi] pre ! cur){Swap(a[cur], a[pre]);}cur;}Swap(a[keyi], a[pre]);keyi pre;return keyi;
}
void QuickSort(int* a, int begin,int end)
{if (begin end){return;}int keyi PartSort3(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi1, end);
}
int main()
{int a[] { 5,7,4,3,10,8,2,6,9,1 };QuickSort(a, 0,(sizeof(a) / sizeof(int))-1);return 0;
}
