# Data Structure_Sort Algorithm

## 排序算法

### 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

0 条评论

• ### Sort Algorithm

生成随机的n个数量的数组，输出数组每一个元素的内容。测试排序算法使用的标准就是运行时间和排序的正确性，所以需要一个验证正确性和计算排序时间的：

• ### Sort Algorithm排序算法

第一次迭代，寻找0到6个下标的数字哪个是最小的，找到最小的就和第一个交换，也就是2。第一次遍历所有

• ### Some methods of deep learning and dimensionality reduction

上一篇主要是讲了全连接神经网络，这里主要讲的就是深度学习网络的一些设计以及一些权值的设置。神经网络可以根据模型的层数，模型的复杂度和神经元的多少大致可以分成两类...

• ### Sort Algorithm

生成随机的n个数量的数组，输出数组每一个元素的内容。测试排序算法使用的标准就是运行时间和排序的正确性，所以需要一个验证正确性和计算排序时间的：

• ### 排序算法算法对比

排序大的分类可以分为两种：内排序和外排序。在排序过程中，全部记录存放在内存，则称为内排序，如果排序过程中需要使用外存，则称为外排序。下面讲的排序都是属于内排序。...

• ### [图解] 堆排序

大根堆与数组的关系：计算机中是没有堆或者树这种概念的，堆或者树需要使用基本的数据结构来实现，用数组表示一个大根堆的规律如下：

• ### 你对JavaScript的Array对象了解有多少？

工作中，数组应用非常广泛，菜单、列表、banner图等等都会应用到数组，所以必须对数组的属性和方法非常熟练才OK，下面一起来了解一下。

• ### 冒泡排序、选择排序、插入排序

冒泡排序：每次遍历后选出最大的元素，每当选出一个下次遍历就排除之前已选的最大元素，因为每次遍历都能定位一个最大元素。

• ### 必学十大经典排序算法，看这篇就够了(附完整代码/动图/优质文章)

十大排序算法可以说是每个程序员都必须得掌握的了，花了一天的时间把代码实现且整理了一下，为了方便大家学习，我把它整理成一篇文章，每种算法会有简单的算法思想描述，为...