锛堜竴锛夌洰鏍?/p>
鍦ㄥ疄闄呴棶棰樼殑瑙ｅ喅杩囩▼涓紝鎴戜滑鍙戠幇锛屽緢澶氶棶棰橀兘鍙互褰掔粨涓哄鏁版嵁鐨勬帓搴忓拰鏌ヨ銆傝�屾煡璇㈢殑鏁堢巼鍒欏湪寰?/p>
澶х▼搴︿笂渚濊禆浜庢帓搴忕殑鏁堢巼锛涘挨鍏舵槸鍦ㄦ暟鎹噺杈惧埌娴烽噺绾х殑鏃跺�欍�傚洜姝わ紝璁捐涓�涓湁鏁堢殑鎺掑簭绠楁硶鏄嚦鍏?/p>
閲嶈鐨勩�傛湰鏂囪璁′簡涓�涓�氱敤鐨?/p>
c++ quicksort
妯℃澘绫汇�傞�氳繃绠�鍗曠殑鎻愪緵涓�涓?/p>
data
绫伙紝鍙互瀹炵幇浠绘剰鏁版嵁鐨?/p>
蹇�熸帓搴忕畻娉曪紝鎻愰珮浜嗗紑鍙戞晥鐜囥�?/p>
锛堜簩锛夊揩閫熸帓搴忕畻娉曠殑鎬濇兂
鏈�鍩烘湰鐨勫揩閫熸帓搴忕殑鎬濇兂鏄熀浜庡垎娌荤瓥鐣ョ殑锛?/p>
瀵逛簬杈撳叆鐨勫瓙搴忓垪
l[p..r]
锛屽鏋滆妯¤冻澶熷皬鍒欑洿鎺ヨ繘琛屾帓搴忥紝鍚﹀垯鍒嗕笁姝ュ鐞嗭細
1
鍒嗚В
(divide)
锛氬皢杈撳叆鐨勫簭鍒?/p>
l[p..r]
鍒掑垎鎴愪袱涓潪绌哄瓙搴忓垪
l[p..q]
鍜?/p>
l[q+1..r]
锛?/p>
浣?/p>
l[p..q]
涓换涓�鍏冪礌鐨勫�间笉
澶т簬
l[q+1..r]
涓换涓�鍏冪礌鐨勫�笺�?/p>
2
閫掑綊姹傝В
(conquer)
锛氶�氳繃閫掑綊璋冪敤蹇�熸帓搴忕畻娉曞垎鍒
l[p..q]
鍜?/p>
l[q+1..r]
杩涜鎺掑簭銆?/p>
3
鍚堝苟
(merge)
锛氱敱浜庡鍒嗚В鍑虹殑涓や釜瀛愬簭鍒楃殑鎺掑簭鏄氨鍦拌繘琛岀殑锛?/p>
鎵�浠ュ湪
l[p..q]
鍜?/p>
l[q+1..r]
閮芥帓濂藉簭鍚庝笉
闇�瑕佹墽琛屼换浣曡绠?/p>
l[p..r]
灏卞凡鎺掑ソ搴忋�?/p>
锛堜笁锛夊噯澶囧伐浣滃拰婧愪唬鐮?/p>
1
浣跨敤
vc6
寤虹珛
console
宸ョ▼
2
鍔犲叆涓嬮潰鐨勬ā鏉跨被锛堝揩閫熸帓搴忕殑妯℃澘绫汇�?/p>
锛?/p>
锛?/p>
template<typename datatype>//datatype
鏄ā鏉垮弬鏁帮紝浠ｈ〃浜嗘鎺掑簭鐨勬暟鎹被鍨?/p>
class quicksorttemp
{
public:
quicksorttemp()
{
}
~quicksorttemp()
{
}
public:
//
蹇�熸帓搴忕殑瀹炵幇锛?/p>
array
鏄鎺掑簭鏁版嵁鐨勬暟缁勶紝
nlower
锛?/p>
nupper
鑼冨洿鏄?/p>
0 ~
鏁版嵁鎬讳釜鏁?/p>
-1
static void quicksort(datatype* array, int nlower, int nupper)
{
//
娴嬭瘯鏄惁鎺掑簭瀹屾瘯
if (nlower < nupper)
{
//
鍒嗚В鍜屽垎鍒繘琛屾帓搴?/p>
int nsplit = partition (array, nlower, nupper);//
鏁版嵁鍒囧垎涓轰袱涓儴鍒?/p>
quicksort (array, nlower, nsplit - 1);//
宸﹀崐閮ㄥ垎閫掑綊鎺掑簭
quicksort (array, nsplit + 1, nupper);//
鍙冲崐閮ㄥ垎閫掑綊鎺掑簭
}
}
//
鍒囧垎鏁版嵁涓哄乏鍙充袱涓儴鍒嗭紝杩斿洖涓棿鍏冪礌
x
鐨勭紪鍙?/p>