|
这两天复习了一下排序方面的知识，现将目前比较常见的几种排序方法整理一下。
选择排序的思想是首先先找到序列中最大元素并将它与序列中最后一个元素交换，然后找下一个最大元素并与倒数第二个元素交换，依次类推。此排序很简单，这不做多说，代码实现如下：
1 void selectionSort(int data[],size_t n)
2 {
3 size_t i,j;
4 size_t MaxValIndex;
5 int largest;
6 if (0==n)
7 {
8 cout<<"Don't exist datas!"<<endl;
9 return;
10 }
11 for (i=n-1;i>0;i--)
12 {
13 largest=data[0];
14 MaxValIndex=0;
15 for (j=0;j<=i;j++)
16 {
17 if (largest<data[j])
18 {
19 largest=data[j];
20 MaxValIndex=j;
21 }
22 }
23 swap(data[i],data[MaxValIndex]);
24 }
25 }
算法流程：
1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到下一位置中
6. 重复步骤2
void insertSort(int data[],size_t n)
{
size_t i,j;
int next;
for (i=1;i<n;i++)
{
next=data[i];
j=i;
while(j>0 && next<data[j-1])
{
data[j]=data[j-1];
j--;
}
data[j]=next;
}
}
依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。
1 void BubbleSort(int data[],size_t n)
2 {
3 bool flag=true;
4 size_t k;
5 k=n;
6 size_t i;
7 while(flag)
8 {
9 flag=false;
10 for (i=1;i<k;i++)
11 {
12 if (data[i-1]>data[i])
13 {
14 swap(data[i-1],data[i]);
15 flag=true;
16 }
17 }
18 k--;
19 }
20 }
在介绍合并排序之前，首先介绍下递归设计的技术，称为分治法。分治法的核心思想是：当问题比较小时，直接解决。当问题比较大时，将问题分为两个较小的子问题，每个子问题约为原来的一半。使用递归调用解决每个子问题。递归调用结束后，常常需要额外的处理，将较小的问题的结果合并，得到较大的问题的答案。
合并排序算法在接近数组中间的位置划分数组，然后使用递归运算对两个一半元素构成的数组进行排序，最后将两个子数组进行合并，形成一个新的已排好序的数组。
代码如下：
1 void mymerge(int data[],size_t n1,size_t n2)
2 {
3 size_t i;
4 int *temp;
5 size_t copied=0;
6 size_t copied1=0;
7 size_t copied2=0;
8 temp =new int[n1+n2];
9 while(copied1<n1 && copied2< n2)
10 {
11 if (data[copied1]<(data+n1)[copied2])
12 {
13 temp[copied]=data[copied1];
14 copied1++;
15 copied++;
16 }
17 else
18 {
19 temp[copied]=(data+n1)[copied2];
20 copied2++;
21 copied++;
22 }
23 }
24 while(copied1<n1)
25 {
26 temp[copied]=data[copied1];
27 copied1++;
28 copied++;
29 }
30 while(copied2<n2)
31 {
32 temp[copied]=(data+n1)[copied2];
33 copied2++;
34 copied++;
35 }
36 for (i=0;i<n1+n2;i++)
37 {
38 data[i]=temp[i];
39 }
40 delete []temp;
41
42 }
43
44 void mergeSort(int data[],size_t n)
45 {
46 size_t n1,n2;
47
48 if (n>1)
49 {
50 n1=n/2;
51 n2=n-n1;
52 mergeSort(data,n1);
53 mergeSort((data+n1),n2);
54 mymerge(data,n1,n2);
55 }
56 }
快速排序与合并排序有着很多相似性。将要排序的数组分成两个子数组，通过两次递归调用分别对两个数组进行排序，再将已经排好序的两个数组合并成一个独立的有序数组。但是，将数组一分为二的做法比合并排序中使用的简单方法复杂的多。它需要将所有小于或者等于基准元素的元素放置到基准元素前面的位置，将大于基准的元素放置到基准后面的位置。
1 /******快速排序***********/
2 void partition_yl(int data[],size_t n,size_t &pivot_index)
3 {
4 size_t pivot=data[0];
5 size_t big_index=1;
6 size_t small_index=n-1;
7 while(big_index<=small_index)
8 {
9 if(big_index<n && data[big_index]<=pivot)
10 {
11 big_index++;
12 }
13 if (small_index>0 && data[small_index]>pivot)
14 {
15 small_index--;
16 }
17 if (big_index<small_index)
18 {
19 swap(data[big_index],data[small_index]);
20 }
21 }
22 pivot_index=small_index;
23 data[0]=data[pivot_index];
24 data[pivot_index]=pivot;
25 }
26 void quickSort(int data[],size_t n)
27 {
28 size_t pivot_index;
29 size_t n1,n2;
30 if (n>1)
31 {
32 partition_yl(data,n,pivot_index);
33 n1=pivot_index;
34 n2=n-n1-1;
35 quickSort(data,n1);
36 quickSort((data+pivot_index+1),n2);
37
38 }
39 }
1 inline size_t parent(size_t k)
2 {
3 return (k-1)/2;
4 }
5 void make_heap(int data[],size_t n)
6 {
7 size_t i,k;
8 for (i=1;i<n;i++)
9 {
10 k=i;
11 while(data[k]>data[parent(k)] &&k!=0)
12 {
13 swap(data[k],data[parent(k)]);
14 k=parent(k);
15 }
16 }
17 }
18
19 void reheapify_down(int data[],size_t n)
20 {
21 size_t current;
22 size_t child_index;
23 bool heap_ok;
24 current=0;
25 heap_ok=false;
26 while((!heap_ok) && (2*current+1<n || 2*current+2<n))
27 {
28 if (2*current+1<n && 2*current+2>=n)
29 {
30 child_index=2*current+1;
31 }
32 else
33 {
34 if (data[2*current+1]>data[2*current+2])
35 {
36 child_index=2*current+1;
37 }
38 else
39 {
40 child_index=2*current+2;
41 }
42
43 }
44 if (data[current]<data[child_index])
45 {
46 swap(data[current],data[child_index]);
47 current=child_index;
48 }
49 else
50 {
51 heap_ok=true;
52 }
53 }
54 }
55
56 /****堆排序******/
57 void heapSort(int data[],size_t n)
58 {
59 size_t unsorted=n;
60 make_heap(data,n);
61 while(unsorted>1)
62 {
63 unsorted--;
64 swap(data[0],data[unsorted]);
65 reheapify_down(data,unsorted);
66 }
67 }
大概常用的几种排序就这几种，希望大家多多指正。
|
