?? qsort4.txt
字號:
//**************************************
//
// Name: Template Quick Sort
// Description:Quickly sort any number o
// f data elements of any type into ascendi
// ng or descending order.
// By: Alex Schwendner
//
// Inputs:- bool ascending
if true, the data will be sorted into
ascending order. if false, the data
will be sorted into descending order.
- type *first_ptr
A pointer to the first data element in
the list. Can be of any type as long
as the operators =, ==, !=, <, and >
are defined for the data type.
- int number
The total number of elements to be sorted.
//
// Assumes:The data elements are at cons
// ecutive memory locations, such as in an
// array.
//
////////////////////////////////////////
// ////////////////////////////////////////
///////////////////
#ifndef _INC_SORT
#define _INC_SORT
#ifndef _INC_STDLIB
#include <stdlib.h>
#endif
template <class type> inline void sort(bool ascending, type *first_ptr, int number);
template <class type> inline void static sortAscending(type *first_ptr, int number);
template <class type> inline void static sortDescending(type *first_ptr, int number);
// Takes a pointer to an array of types.
//
template <class type> inline void sort(bool ascending, type *first_ptr, int number){
srand(number);
if(ascending){
sortAscending(first_ptr,number - 1);
} else {
sortDescending(first_ptr,number - 1);
}
return;
}
template <class type> inline void static sortAscending(type *first_ptr, int number){
if(number < 1){
return;
}
register type pivot = *(first_ptr + (rand() % (number + 1)));
type temp1 = *(first_ptr + (rand() % (number + 1)));
type temp2 = *(first_ptr + (rand() % (number + 1)));
if(pivot > temp1){
if(pivot > temp2){
if(temp1 > temp2){
pivot = temp1;
} else {
pivot = temp2;
}
}
} else {
if(pivot < temp2){
if(temp1 < temp2){
pivot = temp1;
} else {
pivot = temp2;
}
}
}
type *next_ptr = first_ptr + number;
type swap_int;
bool swap_bool;
for(register type *loop = first_ptr; loop < next_ptr; ++loop){
swap_bool = *loop > pivot;
if(!swap_bool){
if(*loop == pivot){
swap_bool = rand() % 2 == 0;
}
}
if(swap_bool){
while(next_ptr > loop){
if(*next_ptr < pivot){
break;
} else {
if(*next_ptr != pivot){
--next_ptr;
} else {
if(rand() % 2 == 0){
break;
} else {
--next_ptr;
}
}
}
}
swap_int = *loop;
*loop = *next_ptr;
*next_ptr = swap_int;
}
}
if(*next_ptr < pivot){
sortAscending(first_ptr,(next_ptr - first_ptr));
sortAscending(next_ptr + 1,(first_ptr + number - next_ptr - 1));
} else {
sortAscending(first_ptr,(next_ptr - first_ptr - 1));
sortAscending(next_ptr,(first_ptr + number - next_ptr));
}
return;
}
template <class type> inline void static sortDescending(type *first_ptr, int number){
if(number < 1){
return;
}
register type pivot = *(first_ptr + (rand() % (number + 1)));
type *next_ptr = first_ptr + number;
type swap_int;
bool swap_bool;
for(register type *loop = first_ptr; loop < next_ptr; ++loop){
swap_bool = *loop > pivot;
if(!swap_bool){
if(*loop == pivot){
swap_bool = rand() % 2 == 0;
}
}
if(swap_bool){
while(next_ptr < loop){
if(*next_ptr > pivot){
break;
} else {
if(*next_ptr != pivot){
--next_ptr;
} else {
if(rand() % 2 == 0){
break;
} else {
--next_ptr;
}
}
}
}
swap_int = *loop;
*loop = *next_ptr;
*next_ptr = swap_int;
}
}
if(*next_ptr > pivot){
sortAscending(first_ptr,(next_ptr - first_ptr));
sortAscending(next_ptr + 1,(first_ptr + number - next_ptr - 1));
} else {
sortAscending(first_ptr,(next_ptr - first_ptr - 1));
sortAscending(next_ptr,(first_ptr + number - next_ptr));
}
return;
}
#endif /* _INC_SORT */
////////////////////////////////////////
// ////////////////////////////////////////
///////////////////
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -