快速排序Word文档格式.docx
《快速排序Word文档格式.docx》由会员分享,可在线阅读,更多相关《快速排序Word文档格式.docx(33页珍藏版)》请在冰点文库上搜索。
在c++中可以用函数qsort()可以直接为数组进行排序。
[1]
用法:
voidqsort(void*base,intnelem,intwidth,int(*fcmp)(constvoid*,constvoid*));
参数:
1待排序数组首地址
2数组中待排序元素数量
3各元素的占用空间大小
4指向函数的指针,用于确定排序的顺序
快速排序算法示例代码
快速排序算法GO
?
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
//
第一种写法
func
quickSort(values
[]int,
left,
right
int)
{
temp
:
=
values[left]
p
left
i,
j
right
for
i
<
>
&
values[j]
j--
}
if
values[p]
values[j]
j
values[i]
i++
values[i]
i
temp
p-left
1
quickSort(values,
p-1)
right-p
p+1,
right)
QuickSort(values
[]int)
len(values)
return
0,
len(values)-1)
第二种写法
Quick2Sort(values
mid,
values[0],
head,
tail
len(values)-1
head
fmt.Println(values)
mid
values[i],
values[tail]
values[tail],
tail--
}
else
values[head]
values[head],
head++
mid
Quick2Sort(values[:
head])
Quick2Sort(values[head+1:
])
快速排序算法Ruby
def
quick_sort(a)
(x=a.pop)
quick_sort(a.select
{
|i|
x
})
+
[x]
[]
end
快速排序算法Erlang语言
超简短实现:
q_sort([])->
[];
q_sort([H|R])->
q_sort([X||X<
-R,X<
H])++[H]++
-R,X>
=H]).
快速排序算法Haskell语言
q_sort
n=case
n
of
[]->
(x:
xs)->
[a|a<
-xs,a<
=x]++[x]++q_sort
-xs,a>
x]
快速排序算法C++语言
#include
iostream>
using
namespace
std;
void
Qsort(int
a[],
int
low,
high)
if(low
return;
first
low;
last
high;
key
a[first];
/*用字表的第一个记录作为枢轴*/
while(first
last)
a[last]
key)
--last;
a[first]
a[last];
/*将比第一个小的移到低端*/
++first;
/*将比第一个大的移到高端*/
key;
/*枢轴记录到位*/
Qsort(a,
first-1);
first+1,
high);
main()
a[]
{57,
68,
59,
52,
72,
28,
96,
33,
24};
sizeof(a)
/
sizeof(a[0])
-
1);
/*这里原文第三个参数要减1否则内存越界*/
for(int
0;
sizeof(a[0]);
i++)
cout
a[i]
"
;
return
}/*参考数据结构p274(清华大学出版社,严蔚敏)*/
快速排序算法C语言版本
sort(int
*a,
if(left
right)/*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/
left;
right;
a[left];
while(i
j)
/*控制在当组内寻找一遍*/
a[j])
/*而寻找结束的条件就是,1,找到一个小于或者大于key的数(大于或小于取决于你想升
序还是降序)2,没有符合条件1的,并且i与j的大小没有反转*/
j--;
/*向前寻找*/
a[j];
/*找到一个这样的数后就把它赋给前面的被拿走的i的值(如果第一次循环且key是
a[left],那么就是给key)*/
a[i])
/*这是i在当组内向前寻找,同上,不过注意与key的大小关系停止循环和上面相反,
因为排序思想是把数往两边扔,所以左右两边的数大小与key的关系相反*/
i++;
a[j]
a[i];
/*当在当组内找完一遍以后就把中间数key回归*/
sort(a,
/*最后用同样的方式对分出来的左边的小组进行同上的做法*/
1,
right);
/*用同样的方式对分出来的右边的小组进行同上的做法*/
/*当然最后可能会出现很多分左右,直到每一组的i
为止*/
快速排序算法JavaScript
function
quickSort(array){
sort(prev,
numsize){
var
nonius
prev;
numsize
-1;
flag
array[prev];
((numsize
prev)
1)
while(nonius
j){
for(;
j;
j--){
(array[j]
flag)
array[nonius++]
array[j];
//a[i]
+=
1;
break;
};
for(
nonius++){
(array[nonius]
flag){
array[j--]
array[nonius];
array[nonius]
flag;
sort(0,
nonius);
sort(nonius
numsize);
array.length);
array;
快速排序算法Java
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
class Quick
public void sort(int arr[],int low,int high)
{
int l=low;
int h=high;
int povit=arr[low];
while(l<
h)
h&
arr[h]>
=povit)
h--;
if(l<
h){
int temp=arr[h];
arr[h]=arr[l];
arr[l]=temp;
l++;
}
arr[l]<
print(arr);
System.out.print("
l="
+(l+1)+"
h="
+(h+1)+"
povit="
+povit+"
\n"
);
if(l>
low)sort(arr,low,l-1);
if(h<
high)sort(arr,l+1,high);
/*//////////////////////////方式二////////////////////////////////*/
更高效点的代码:
public<
TextendsComparable<
superT>
T[]quickSort(T[]targetArr,intstart,intend)
inti=start+1,j=end;
Tkey=targetArr[start];
SortUtil<
T>
sUtil=newSortUtil<
();
if(start>
=end)return(targetArr);
/*从i++和j--两个方向搜索不满足条件的值并交换
*
*条件为:
i++方向小于key,j--方向大于key
*/
while(true)
while(targetArr[j].compareTo(key)>
0)j--;
while(targetArr[i].compareTo(key)<
0&
i<
j)i++;
if(i>
=j)break;
sUtil.swap(targetArr,i,j);
if(targetArr[i]==key)
}else{
/*关键数据放到‘中间’*/
sUtil.swap(targetArr,start,j);
if(start<
i-1)
this.quickSort(targetArr,start,i-1);
if(j+1<
end)
this.quickSort(targetArr,j+1,end);
returntargetArr;
/*//////////////方式三:
减少交换次数,提高效率/////////////////////*/
private<
voidquickSort(T[]targetArr,intstart,intend)
inti=start,j=end;
while(i<
j)
/*按j--方向遍历目标数组,直到比key小的值为止*/
while(j>
i&
targetArr[j].compareTo(key)>
=0)
if(i<
/*targetArr[i]已经保存在key中,可将后面的数填入*/
targetArr[i]=targetArr[j];
/*按i++方向遍历目标数组,直到比key大的值为止*/
j&
targetArr[i].compareTo(key)<
/*此处一定要小于等于零,假设数组之内有一亿个1,0交替出现的话,而key的值又恰巧是1的话,那么这个小于等于的作用就会使下面的if语句少执行一亿次。
/*targetArr[j]已保存在targetArr[i]中,可将前面的值填入*/
targetArr[j]=targetArr[i];
/*此时i==j*/
targetArr[i]=key;
/*递归调用,把key前面的完成排序*/
/*递归调用,把key后面的完成排序*/
快速排序算法C#
System;
System.Collections.Generic;
System.Linq;
System.Text;
test
class
QuickSort
static
Main(string[]
args)
int[]
array
49,
38,
65,
97,
76,
13,
27
sort(array,
array.Length
Console.ReadLine();
/**一次排序单元,完成此方法,key左边都比key小,key右边都比key大。
**@param
array排序数组
**@