Data Structure_Sort Algorithm

0
0
0
1. 云栖社区>
2. 博客>
3. 正文

## 排序算法

### Tool implement

``````   //generate a array of n elements, range [rangL, rangeR]
int *generateRandomArray(int n, int rangL, int rangeR) {
assert(rangeR >= rangL);
int *arr = new int[n];
srand(time(NULL));
for (int i = 0; i < n; i++) {
arr[i] = rand() % (rangeR - rangL + 1) + rangL;
}
return arr;
}

template<typename T>
void showArray(T arr[], int n) {
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
``````

``````    template<typename T>
void testSort( string sortName, void(*sort)(T[], int), T arr[], int n){
clock_t startTime = clock();
sort(arr, n);
clock_t endTime = clock();
if (isSorted(arr, n)){
cout << sortName << ": " << double(endTime - startTime)/CLOCKS_PER_SEC << "s" << endl;
} else
cout << "sort function is wrong!" << endl;
return;
}

template<typename T>
bool isSorted(T arr[], int n){
for (int i = 0; i < n-1; i++){
if (arr[i] > arr[i+1])
return false;
}
return true;
}
``````

### 的排序

#### 选择排序——SelectionSort

``````template<typename T>
void SelectionSort(T arr[], int n) {
for (int i = 0; i < n; i++) {
int minIndex = i;
for (int j = i; j < n; j++) {
if (arr[j] < arr[minIndex])
minIndex = j;
}
swap(arr[minIndex], arr[i]);
}
}

``````

``````    struct student{
string name;
float score;

bool operator<(const student &otherStudent){
return score < otherStudent.score;
}

friend ostream& operator<<(ostream &os, const student &otherStudent){
os << "Student: " << otherStudent.name << " " << otherStudent.score << endl;
return os;
}
};

``````

#### 插入排序——InsertionSort

``````template<typename T>
void InsertionSort(T arr[], int n){
for (int i = 1; i < n; i ++){
for (int j = i; j > 0; j --){
if (arr[j] < arr[j-1]){
swap(arr[j], arr[j-1]);
} else
break;
}
}
}
``````

``````template<typename T>
void InsertionSort_version2(T arr[], int n){
for (int i = 1; i < n; i ++){
T temp = arr[i];
int j = 0;
for (j = i; j > 0 && arr[j-1] > temp; j --){
arr[j] = arr[j-1];
}
arr[j] = temp;
}
``````

### 的排序

#### 归并排序——MergeSort

，归并的时候就是

``````template<typename T>
void __merge(T arr[], int l, int mid, int r) {
T *temp = new T[r-l+1];
for (int i = l; i <= r; i++) {
temp[i - l] = arr[i];
}
int i = l, j = mid + 1;
for (int k = l; k <= r; k++) {
if (i > mid) {
arr[k] = temp[j - l];
j++;
} else if (j > r) {
arr[k] = temp[i - l];
i++;
} else if (temp[i - l] < temp[j - l]) {
arr[k] = temp[i - l];
i++;
} else {
arr[k] = temp[j - l];
j++;
}
}
delete[] temp;
}

template<typename T>
void __mergeSort(T arr, int l, int r) {
if (l >= r) {
return;
} else {
int mid = (l + r) / 2;
__mergeSort(arr, l, mid);
__mergeSort(arr, mid + 1, r);
__merge(arr, l, mid, r);
}
}

template<typename T>
void MergeSort(T arr[], int n) {
__mergeSort(arr, 0, n - 1);
}
``````

``````void __mergeSort(T arr, int l, int r) {
if (l >= r) {
return;
} else {
int mid = (l + r) / 2;
__mergeSort(arr, l, mid);
__mergeSort(arr, mid + 1, r);
if (arr[mid] > arr[mid + 1]) {
__merge(arr, l, mid, r);
}
}
}
``````

#### 自底向上的归并排序——upMergeSort

``````template<typename T>
void upMergeSort(T arr[], int n){
for (int sz = 1; sz <= n; sz = sz + sz){
for (int i = 0; i + sz < n; i += sz + sz){
__merge(arr, i, i+sz-1, min(i+sz+sz-1, n-1));
}
}
}
``````

#### 快速排序——QuickSort

v是要分割的数字，e就是当前要判断的数字。有两个情况要判断，如果是大于V的，那就简单了，直接i++，如果是小于V，那就把i和j+1的数字进行交换即可，然后j++，最后i++即可。

``````template<typename T>
int __partition(T arr[], int l, int r) {
T v = arr[l];
int j = l;
for (int i = l + 1; i <= r; i++) {
if (arr[i] < v) {
swap(arr[j + 1], arr[i]);
j++;
}
}
swap(arr[j], arr[l]);
return j;
}

template<typename T>
void __quickSort(T arr[], int l, int r) {
if (l >= r) {
return;
}
int p = __partition(arr, l, r);
__quickSort(arr, l, p - 1);
__quickSort(arr, p + 1, r);
}

template<typename T>
void QuickSort(T arr[], int n) {
__quickSort(arr, 0, n - 1);
}

``````

.可以看到效果还是有的。快速排序之所以是

``````template<typename T>
int __partition(T arr[], int l, int r) {
swap(arr[l], arr[rand()%(r-l+1)+l]);
T v = arr[l];
int j = l;
for (int i = l + 1; i <= r; i++) {
if (arr[i] < v) {
swap(arr[j + 1], arr[i]);
j++;
}
}
``````

``````template<typename T>
int __partition_version2(T arr[], int l, int r) {
swap(arr[l], arr[rand() % (r - l + 1) + l]);
T v = arr[l];
int i = l+1, j = r;
while (true){
while (i <= r && arr[i] < v){
i++;
}
while (j >= l+1 && arr[j] > v){
j--;
}
if (i > j){
break;
} else{
swap(arr[i], arr[j]);
i++;
j--;
}
}
swap(arr[l], arr[j]);
return j;
}
``````

``````
template<typename T>
int __partition_version3(T arr[], int l, int r){
swap(arr[l], arr[rand() % (r - l + 1) + l]);
T v = arr[l];
int lt = l, gt = r+1, i = l+1;
while (i < gt){
if (arr[i] < v){
swap(arr[i], arr[lt+1]);
lt++;
i++;
} else if (arr[i] > v){
swap(arr[i], arr[gt-1]);
gt--;
} else{
i++;
}
}
swap(arr[l], arr[lt]);
return lt;
}
``````

#### 堆排序——HeapSort

``````using namespace std;
template<typename T>
void HeapSort_version1(T arr[], int n){
MaxHeap<T> heap = MaxHeap<T>(n);
for (int i = 0; i < n; ++i) {
heap.insert(arr[i]);
}
for (int j = n-1; j >= 0; --j) {
arr[j] = heap.pop();
}
}
``````

``````    MaxHeap(item arr[], int n){
data = new item[n+1];
capacity = n;
for (int i = 0; i < n; ++i) {
data[i+1] = arr[i];
}
count = n;
for (int j = count/2; j >= 1; --j) {
shiftDown(j);
}
}
``````

，而使用heapify的复杂度是
。上面的排序每一次都是复制一个数组出来排序，但是如果原地在原数组上进行排序，速度是可以快很多的，这个就是原地堆排序。

``````template<typename T>
void __shiftDown(T arr[], int n, int i){
while (2*i + 1 < n){
int change = 2*i + 1;
if (change + 1 < n && arr[change] < arr[change+1]){
change ++;
}
if (arr[i] >= arr[change]){
break;
}
swap(arr[i], arr[change]);
i = change;
}
}

``````

``````template<typename T>
void HeapSort_version2(T arr[], int n) {
//heapify,create a max heap;
for (int i = (n-1)/2; i >= 0; --i) {
__shiftDown(arr, n, i);
}
for (int j = n-1; j > 0 ; --j) {
swap(arr[0], arr[j]);
__shiftDown(arr, j, 0);
}
}
``````

Insertion Sort
Merge Sort
Quick Sort
Heap Sort

+ 关注