排序算法

插入排序

选择排序

希尔排序

【相关实验】

1. template<class?Record>??
2. Sortable_list<Record>::Sortable_list(const?Record?A[],int?size)??
3. {??
4. ????for(int?i=0;i<size;i++)??
5. ????????insert(i,A[i]);??
6. }??

template<class Record>
Sortable_list<Record>::Sortable_list(const Record A[],int size)
{
	for(int i=0;i<size;i++)
		insert(i,A[i]);
}

1. template<class?Record>??
2. void?Sortable_list<Record>::shell_sort()??
3. /*Post:?The?entries?of?the?Sortable_list?have?been?rearranged?so?that?the?keys?in??
4. ????????all?the?entries?are?sorted?into?nondecreasing?order.?
5. ??Uses:?sort_interval.?
6. */??
7. {??
8. ????int?increment,???//spacing?of?entries?in?sublist??
9. ????????start;???????//starting?point?of?sublist??
10. ????increment=count;??
11. ????do{??
12. ????????increment=increment/2;??
13. ????????for(start=0;start<increment;start++){??
14. ????????????sort_interval(start,increment);??//modified?insertion?sort??
15. ????????????traverse(print_out);??
16. ????????????cout<<endl;??
17. ????????}??
18. ????}while(increment>1);??
19. }??
20. ??
21. template<class?Record>??
22. void?Sortable_list<Record>::sort_interval(int?start,int?increment)??
23. {??
24. ????Sortable_list<Record>?temp;??
25. ????int?j=0;??
26. ????for(int?i=start;i<size();i=i+increment){??
27. ????????Record?temp_record;??
28. ????????retrieve(i,temp_record);??
29. ????????temp.insert(j,temp_record);??
30. ????????j++;??
31. ????}??
32. ????temp.insertion_sort();??
33. ????j=0;??
34. ????for(int?k=start;k<size();k+=increment){??
35. ????????Record?temp_record;??
36. ????????temp.retrieve(j,temp_record);??
37. ????????replace(k,temp_record);??
38. ????????j++;??
39. ????}??
40. }??
41. template<class?Record>??
42. void?Sortable_list<Record>::insertion_sort()??
43. /*Post:?The?entries?of?the?Sortable_list?have?been?rearranged?so?that?the?keys?in?
44. ????????all?the?entries?are?sorted?into?nondecreasing?order.?
45. ??Uses:?Methods?for?the?class?Record;?the?contiguous?List??
46. */??
47. {??
48. ????int?first_unsorted;????????????//position?of?first?unsorted?entry??
49. ????int?position;??????????????????//searches?sorted?part?of?list??
50. ????Record?current;????????????????//holds?the?entry?emporarily?removed?from?list??
51. ????for(first_unsorted=1;first_unsorted<count;first_unsorted++)??
52. ????????if(entry[first_unsorted]<entry[first_unsorted-1]){??
53. ????????????position=first_unsorted;??
54. ????????????current=entry[first_unsorted];?//Pull?unsorted?entry?out?of?the?list.??
55. ????????????do{????????????????????//Shift?all?entries?until?the?proper?position?is?found??
56. ????????????????entry[position]=entry[position-1];??
57. ????????????????position--;?????????//position?if?empty.??
58. ????????????}while(position>0&&entry[position-1]>current);??
59. ????????????entry[position]=current;??
60. ????????}??
61. }??
62. //其他辅助函数见源文件??

template<class Record>
void Sortable_list<Record>::shell_sort()
/*Post: The entries of the Sortable_list have been rearranged so that the keys in 
        all the entries are sorted into nondecreasing order.
  Uses: sort_interval.
*/
{
	int increment,//spacing of entries in sublist
		start;       //starting point of sublist
	increment=count;
	do{
		increment=increment/2;
		for(start=0;start<increment;start++){
			sort_interval(start,increment);  //modified insertion sort
			traverse(print_out);
			cout<<endl;
		}
	}while(increment>1);
}

template<class Record>
void Sortable_list<Record>::sort_interval(int start,int increment)
{
	Sortable_list<Record> temp;
	int j=0;
	for(int i=start;i<size();i=i+increment){
		Record temp_record;
		retrieve(i,temp_record);
		temp.insert(j,temp_record);
		j++;
	}
	temp.insertion_sort();
	j=0;
	for(int k=start;k<size();k+=increment){
		Record temp_record;
		temp.retrieve(j,temp_record);
		replace(k,temp_record);
		j++;
	}
}
template<class Record>
void Sortable_list<Record>::insertion_sort()
/*Post: The entries of the Sortable_list have been rearranged so that the keys in
        all the entries are sorted into nondecreasing order.
  Uses: Methods for the class Record; the contiguous List 
*/
{
	int first_unsorted;            //position of first unsorted entry
	int position;                  //searches sorted part of list
	Record current;                //holds the entry emporarily removed from list
	for(first_unsorted=1;first_unsorted<count;first_unsorted++)
		if(entry[first_unsorted]<entry[first_unsorted-1]){
			position=first_unsorted;
			current=entry[first_unsorted]; //Pull unsorted entry out of the list.
			do{                    //Shift all entries until the proper position is found
 				entry[position]=entry[position-1];
				position--;         //position if empty.
			}while(position>0&&entry[position-1]>current);
			entry[position]=current;
		}
}
//其他辅助函数见源文件

【实验结果】

归并排序

【相关实验】

1. template<class?Record>??
2. void?Sortable_list<Record>::merge(int?low,int?high)??
3. {??
4. ????Record?*tmp=new?Record[high-low+1];??
5. ????int?index=0;??
6. ????int?index1=low,mid=(low+high)/2,index2=mid+1;??
7. ????while(index1<=mid&&index2<=high){??
8. ????????if(entry[index1]<entry[index2])??
9. ????????????tmp[index++]=entry[index1++];??
10. ????????else??
11. ????????????tmp[index++]=entry[index2++];??
12. ????}??
13. ????while(index1<=mid)??
14. ????????tmp[index++]=entry[index1++];??
15. ????while(index2<=high)??
16. ????????tmp[index++]=entry[index2++];??
17. ????for(index=low;index<=high;index++)??
18. ????????entry[index]=tmp[index-low];??
19. ????delete?[]tmp;??
20. ????traverse(print_out);??
21. ????cout<<endl;??
22. ??????
23. }??
24. ??
25. template<class?Record>??
26. void?Sortable_list<Record>::recursive_merge_sort(int?low,int?high)??
27. /*Post:?The?entries?of?the?sortable?list?between?
28. ????????index?low?and?high?have?been?rearranged?so?that?
29. ????????their?keys?are?sorted?into?nondecreasing?order.?
30. ??Uses:?The?contiguous?list?
31. */??
32. {??
33. ????if(high>low){??
34. ????????recursive_merge_sort(low,(high+low)/2);??
35. ????????recursive_merge_sort((high+low)/2+1,high);??
36. ????????merge(low,high);??
37. ????}??
38. }??
39. ??
40. template<class?Record>??
41. void?Sortable_list<Record>::merge_sort()??
42. /*?Post:?The?entries?of?the?sortable?list?have?been?rearranged?so?that?
43. ?????????their?keys?are?sorted?into?nondecreasing?order.?
44. ???Uses:?The?contiguous?list?
45. */??
46. {??
47. ????recursive_merge_sort(0,size()-1);??
48. }??

template<class Record>
void Sortable_list<Record>::merge(int low,int high)
{
	Record *tmp=new Record[high-low+1];
	int index=0;
	int index1=low,index2=mid+1;
	while(index1<=mid&&index2<=high){
		if(entry[index1]<entry[index2])
			tmp[index++]=entry[index1++];
		else
			tmp[index++]=entry[index2++];
	}
	while(index1<=mid)
		tmp[index++]=entry[index1++];
	while(index2<=high)
		tmp[index++]=entry[index2++];
	for(index=low;index<=high;index++)
		entry[index]=tmp[index-low];
	delete []tmp;
	traverse(print_out);
	cout<<endl;
	
}

template<class Record>
void Sortable_list<Record>::recursive_merge_sort(int low,int high)
/*Post: The entries of the sortable list between
        index low and high have been rearranged so that
		their keys are sorted into nondecreasing order.
  Uses: The contiguous list
*/
{
	if(high>low){
		recursive_merge_sort(low,(high+low)/2);
		recursive_merge_sort((high+low)/2+1,high);
		merge(low,high);
	}
}

template<class Record>
void Sortable_list<Record>::merge_sort()
/* Post: The entries of the sortable list have been rearranged so that
         their keys are sorted into nondecreasing order.
   Uses: The contiguous list
*/
{
	recursive_merge_sort(0,size()-1);
}

【实验结果】

快速排序

【相关实验】

1. template<class?Record>??
2. int?Sortable_list<Record>::partition(int?low,int?high)??
3. /*Pre:??low?and?high?are?valid?positions?of?the?Sortable_list,?with?low<=high.?
4. ??Post:?The?center?(or?left?center)?entry?in?the?range?between?indices?low?and??
5. ????????high?of?the?Sortable_list?has?been?chosen?as?a?pivot.?All?entries?of?the?
6. ????????Sortable_list?between?indices?low?and?high,?inclusive,?have?been?rearranged?
7. ????????so?that?chosen?with?keys?less?than?the?pivot?com?before?the?pivot?
8. ????????and?the?remaining?entries?come?after?the?pivot.?The?final?position?of?the??
9. ????????pivot?is?returned.?
10. ?Uses:?swap(int,int?j)?contigious?list?
11. */??
12. {??
13. ????Record?pivot;??
14. ????int?i,???????????//used?to?scan?through?the?list??
15. ????????last_small;??//position?of?the?last?key?less?than?pivot??
16. ????swap(low,(low+high)/2);??
17. ????pivot=entry[low];??
18. ????last_small=low;??
19. ????for(i=low+1;i<=high;i++)??
20. ????//At?the?beginning?of?each?iteration?of?this?loop,?we?have?the?following?conditions:??
21. ????//????If?low<j<=last_samll?then?entry[j].key<pivot??
22. ????//????If?last_small<j<i?then?entry[j].key>=pivot.??
23. ???????if(entry[i]<pivot){??
24. ???????????last_small=last_small+1;??
25. ???????????swap(last_small,i);??//Move?large?entry?to?right?and?small?to?left??
26. ???????}??
27. ????swap(low,last_small);???//Put?the?pivot?into?its?proper?position.??
28. ????return?last_small;??
29. }??
30. ??
31. template<class?Record>??
32. void?Sortable_list<Record>::recursive_quick_sort(int?low,int?high)??
33. /*Pre:??low?and?high?are?valid?positions?in?the?Sortable?list.?
34. ??Post:?The?entries?of?the?Sortable_list?have?been?rearranged?so?that?their?keys?
35. ????????are?sorted?into?nondecreasing?order.?
36. ??Uses:?The?contiguous?list,?recursive_quick_sort,?partition.?
37. */??
38. {??
39. ????int?pivot_postion;??
40. ????if(low<high){??
41. ????????pivot_postion=partition(low,high);??
42. ????????recursive_quick_sort(low,pivot_postion-1);??
43. ????????recursive_quick_sort(pivot_postion+1,high);??
44. ????}??
45. }??
46. ??
47. template<class?Record>??
48. void?Sortable_list<Record>::quick_sort()??
49. {??
50. ????recursive_quick_sort(0,count-1);??
51. }??
52. //其他函数见源码??

template<class Record>
int Sortable_list<Record>::partition(int low,int high)
/*Pre:  low and high are valid positions of the Sortable_list,with low<=high.
  Post: The center (or left center) entry in the range between indices low and 
        high of the Sortable_list has been chosen as a pivot. All entries of the
		Sortable_list between indices low and high,inclusive,have been rearranged
		so that chosen with keys less than the pivot com before the pivot
		and the remaining entries come after the pivot. The final position of the 
		pivot is returned.
 Uses: swap(int,int j) contigious list
*/
{
	Record pivot;
	int i,//used to scan through the list
		last_small;  //position of the last key less than pivot
	swap(low,(low+high)/2);
	pivot=entry[low];
	last_small=low;
	for(i=low+1;i<=high;i++)
	//At the beginning of each iteration of this loop,we have the following conditions:
	//    If low<j<=last_samll then entry[j].key<pivot
	//    If last_small<j<i then entry[j].key>=pivot.
	   if(entry[i]<pivot){
		   last_small=last_small+1;
		   swap(last_small,i);  //Move large entry to right and small to left
	   }
	swap(low,last_small);   //Put the pivot into its proper position.
	return last_small;
}

template<class Record>
void Sortable_list<Record>::recursive_quick_sort(int low,int high)
/*Pre:  low and high are valid positions in the Sortable list.
  Post: The entries of the Sortable_list have been rearranged so that their keys
        are sorted into nondecreasing order.
  Uses: The contiguous list,recursive_quick_sort,partition.
*/
{
	int pivot_postion;
	if(low<high){
		pivot_postion=partition(low,high);
		recursive_quick_sort(low,pivot_postion-1);
		recursive_quick_sort(pivot_postion+1,high);
	}
}

template<class Record>
void Sortable_list<Record>::quick_sort()
{
	recursive_quick_sort(0,count-1);
}
//其他函数见源码

【实验结果】

堆排序

【相关实验】

1. template<class?Record>??
2. void?Sortable_list<Record>::insert_heap(const?Record?¤t,int?low,int?high)??
3. /*Pre:??The?entries?of?the?Sortable_list?between?indices?low+1?and?high,?
4. ????????inclusive,form?a?heap.?The?entry?in?position?low?will?be?discarded.?
5. ??Post:?The?entry?current?has?been?inserted?into?the?Sortabl_list?and?the?entries,?
6. ????????rearranged?so?that?the?entries?between?indices?low?and?high,?inclusive?
7. ????????form?a?heap.?
8. */??
9. {??
10. ????int?large;???????//position?of?child?of?entry[low]?with?the?larger?key??
11. ????large=2*low+1;???//large?is?now?the?left?child?of?low??
12. ????while(large<=high){??
13. ????????if(large<high&&entry[large]<entry[large+1])??
14. ????????????large++;????//large?is?now?the?child?of?low?with?the?largest?key.??
15. ????????if(current>=entry[large])??
16. ????????????break;??????//current?belongs?in?position?low??
17. ????????else{???????????//Promote?entry[large]?and?move?down?the?tree???
18. ????????????entry[low]=entry[large];??
19. ????????????low=large;??
20. ????????????large=2*low+1;??
21. ????????}??
22. ????}??
23. ????entry[low]=current;??
24. ????traverse(print_out);??
25. ????cout<<endl;??
26. }??
27. ??
28. template<class?Record>??
29. void?Sortable_list<Record>::build_heap()??
30. /*Post:?The?entries?of?the?Sortable_list?have?been?rearranged?so?that??
31. ????????it?becomes?a?heap?
32. ??Uses:?The?contiguous?list?and?insert_heap?
33. */??
34. {??
35. ????int?low;??
36. ????for(low=count/2-1;low>=0;low--){??
37. ????????Record?current=entry[low];??
38. ????????insert_heap(current,low,count-1);??
39. ????}??
40. }??
41. ??
42. template<class?Record>??
43. void?Sortable_list<Record>::heap_sort()??
44. /*Post:?The?entries?of?the?Sortable_list?have?been?rearranged?so?that?their?keys?
45. ????????are?sorted?into?nondecreasing?order.?
46. ??Uses:?The?contiguous?list,?build_heap,?insert_heap?
47. */??
48. {??
49. ????Record?current;???????//temporary?storage?for?moving?entries??
50. ????int?last_unsorted;????//Entries?beyond?last_unsorted?have?been?sorted.??
51. ????build_heap();?????????//First?phase:?Turn?the?list?into?a?heap??
52. ????for(last_unsorted=count-1;last_unsorted>0;last_unsorted--){??
53. ????????current=entry[last_unsorted];???//Extract?the?last?entry?from?the?list??
54. ????????entry[last_unsorted]=entry[0];??//Move?top?of?heap?to?the?end??
55. ????????insert_heap(current,last_unsorted-1);??//Restore?the?heap??
56. ????}??
57. }??
58. //其他函数见源码??

template<class Record>
void Sortable_list<Record>::insert_heap(const Record ¤t,int low,int high)
/*Pre:  The entries of the Sortable_list between indices low+1 and high,form a heap. The entry in position low will be discarded.
  Post: The entry current has been inserted into the Sortabl_list and the entries,rearranged so that the entries between indices low and high,inclusive
		form a heap.
*/
{
	int large;       //position of child of entry[low] with the larger key
	large=2*low+1;   //large is now the left child of low
	while(large<=high){
		if(large<high&&entry[large]<entry[large+1])
			large++;    //large is now the child of low with the largest key.
		if(current>=entry[large])
			break;      //current belongs in position low
		else{           //Promote entry[large] and move down the tree 
			entry[low]=entry[large];
			low=large;
			large=2*low+1;
		}
	}
	entry[low]=current;
	traverse(print_out);
	cout<<endl;
}

template<class Record>
void Sortable_list<Record>::build_heap()
/*Post: The entries of the Sortable_list have been rearranged so that 
        it becomes a heap
  Uses: The contiguous list and insert_heap
*/
{
	int low;
	for(low=count/2-1;low>=0;low--){
		Record current=entry[low];
		insert_heap(current,count-1);
	}
}

template<class Record>
void Sortable_list<Record>::heap_sort()
/*Post: The entries of the Sortable_list have been rearranged so that their keys
        are sorted into nondecreasing order.
  Uses: The contiguous list,build_heap,insert_heap
*/
{
	Record current;       //temporary storage for moving entries
	int last_unsorted;    //Entries beyond last_unsorted have been sorted.
	build_heap();         //First phase: Turn the list into a heap
	for(last_unsorted=count-1;last_unsorted>0;last_unsorted--){
		current=entry[last_unsorted];   //Extract the last entry from the list
		entry[last_unsorted]=entry[0];  //Move top of heap to the end
		insert_heap(current,last_unsorted-1);  //Restore the heap
	}
}
//其他函数见源码

【实验结果】

结果分析

【希尔排序】

【归并排序】

【快速排序】

【堆排序】

原文地址：http://www.voidcn.com/article/p-ucctzjhq-vo.html

（编辑：ASP站长网）