排序算法合集

$$FBIWarning:$$

本人没有完整的计算机科班的教育经历，但是一直在兢兢业业，努力学习。

这些排序函数都是自己零零散散写的，也没有经过深思熟虑和优化，纯粹是为了自娱自乐。

1. 冒泡排序：

代码里有两种实现方式，感觉第二种比较正宗，第一种跟插入排序相似度很高。

int bubbleSortInc(int data[], int size) {if (size <= 0){return -1;}for (int i = 0; i <= size - 1; i++) {for (int j = 0; j < i; j++){if (data[j] > data[j + 1]){int tmp = data[j];data[j] = data[j + 1];data[j + 1] = tmp;}}}return 0;
}

int bubbleSortDec(int data[], int size) {if (size <= 0){return -1;}for (int i = size - 1; i >= 0; i--) {for (int j = 0; j < i; j++){if (data[j] > data[j + 1]){int tmp = data[j];data[j] = data[j + 1];data[j + 1] = tmp;}}}return 0;
}

2. 插入排序：

此处可以看出，插入排序和冒泡排序还是有很大的不同。

int insertSort(int data[], int size) {int cnt = 0;if (size <= 1){return 0;}for (int i = 0; i < size - 1; i++){if (data[i] > data[i + 1]){int tmp = data[i + 1];data[i + 1] = data[i];data[i] = tmp;for (int j = i; j > 0; j--){if (data[j] < data[j - 1]){int tmp2 = data[j];data[j] = data[j - 1];data[j - 1] = tmp2;}}}}return cnt;
}

3. 选择排序

按照次序，每次挑选一个最小的，放到相应的次序位置。

int selectLeast(int data[], int datalen, int idx) {for (int i = idx + 1; i < datalen; i++){if (data[idx] > data[i]){idx = i;}}return idx;
}int selectionSort(int data[], int datalen) {for (int i = 0; i < datalen; i++){int least = selectLeast(data, datalen, i);if (least != i) {int tmp = data[i];data[i] = data[least];data[least] = tmp;}}return 0;
}

4. shell排序

void shellInsert(int arr[],int arrsize, int dk) {for (int i = dk ;i <= arrsize - 1;i ++){if (arr[i] < arr[i-dk]){int tmp = arr[i]; int j = i - dk;for (;j >= 0 && tmp < arr[j];j -= dk){arr[j + dk] = arr[j];}arr[j + dk] = tmp;}}
}void shellSort(int arr[], int size, int delta[], int deltasize) {for (int i = 0;i < deltasize; i ++){shellInsert(arr, size, delta[i]);}
}

5. 二分插入排序

void binaryInsertSort(int* data,int size) {for (int i = 1;i < size;i ++){int tmp = data[i];int low = 0;int high = i - 1;while (low <= high) {int m = (low + high ) / 2;if (data[i] < data[m]){high = m - 1;}else {low = m + 1;}}for ( int j = i - 1;j >= high + 1; j --){data[j + 1] = data[j];}data[high + 1] = tmp;}
}

6. 快速排序

快速排序一种是本人自己写的，一种是算法书上的源码。

int partition(int data[], int low, int high) {int  pivot = data[low];while (low < high){while (low < high && data[high] >= pivot) // 从右向左找第一个小于x的数high--;if (low < high)data[low++] = data[high];while (low < high && data[low] < pivot) // 从左向右找第一个大于等于x的数low++;if (low < high)data[high--] = data[low];}data[low] = pivot;return low;
}void quickSort(int s[], int low, int high)
{if (low < high){int pivot = partition(s, low, high);quickSort(s, low, pivot - 1);quickSort(s, pivot + 1, high);}
}

int fastSort(int data[], int left, int right) {if (right - left <= 1){return 0;}int pos = left;int tmp = data[pos];int empty = pos;int low = left;int high = right;while (low < high){while (low < high){if (data[high] > tmp){high--;if (high <= low){break;}}else {data[empty] = data[high];empty = high;high--;break;}}while (low < high){if (low == pos){low++;if (high <= low){break;}}if (data[low] < tmp){low++;if (high <= low){break;}}else {data[empty] = data[low];empty = low;low++;break;}}}data[empty] = tmp;fastSort(data, left, low - 1);fastSort(data, low + 1, right);return 0;
}

7. 堆排序
   堆排序是我最喜欢的一种排序。有3种实现方式（后面两种是我根据算法的思路自己写的）。

void swap(int* a, int* b) {int temp = *b;*b = *a;*a = temp;
}void max_heapify(int arr[], int start, int end) {// 建立父節點指標和子節點指標int dad = start;int son = dad * 2 + 1;while (son <= end) { // 若子節點指標在範圍內才做比較if (son + 1 <= end && arr[son] < arr[son + 1]) // 先比較兩個子節點大小，選擇最大的son++;if (arr[dad] > arr[son]) //如果父節點大於子節點代表調整完畢，直接跳出函數return;else { // 否則交換父子內容再繼續子節點和孫節點比較swap(&arr[dad], &arr[son]);dad = son;son = dad * 2 + 1;}}
}void heap_sort(int arr[], int len) {int i;// 初始化，i從最後一個父節點開始調整for (i = len / 2 - 1; i >= 0; i--)max_heapify(arr, i, len - 1);// 先將第一個元素和已排好元素前一位做交換，再重新調整，直到排序完畢for (i = len - 1; i > 0; i--) {swap(&arr[0], &arr[i]);max_heapify(arr, 0, i - 1);}
}

void swap(int& i, int& k) {int tmp = k;k = i;i = tmp;
}void heapAdjust(int arr[], int num, int arrsize) {int pos = num;for (int j = 2 * num + 1; j < arrsize; j = j * 2 + 1){if (j < arrsize - 1 && arr[j] < arr[j + 1]){j++;}if (arr[pos] < arr[j]){break;}else {arr[num] = arr[j];num = j;}}arr[num] = arr[pos];
}void heapSort2(int arr[], int arrsize) {for (int i = arrsize / 2 - 1; i >= 0; i--)		// n/2-1 is previous root dot{heapAdjust(arr, i, arrsize);}for (int i = arrsize - 1; i >= 0; i--){swap(arr[0], arr[i]);heapAdjust(arr, 0, i);}
}

void heapify(int arr[], int arrsize, int num) {int lowest = num;int lchild = 2 * num + 1;	//lchildint rchild = 2 * num + 2;	//rchildif (lchild < arrsize && arr[lchild] > arr[lowest]){lowest = lchild;}if (rchild < arrsize && arr[rchild]> arr[lowest]){lowest = rchild;}if (lowest != num){swap(arr[num], arr[lowest]);heapify(arr, arrsize, lowest);}
}
//				0
//		1				2
//	3		4		5		6
//7	 8    9  10   11 12   13 14void heapSort(int arr[], int arrsize) {for (int i = arrsize / 2 - 1; i >= 0; i--)		// n/2-1 is previous root dot{heapify(arr, arrsize, i);}for (int i = arrsize - 1; i >= 0; i--){swap(arr[0], arr[i]);heapify(arr, i, 0);}
}

8. 归并排序

void Merge(int* data, int i, int m, int n) {int j = 0;int k = 0;for (int j = m + 1, k = i; i < m && j <= n; ++k){if (data[i] <= data[j]){data[k] = data[i++];}else {data[k] = data[j++];}}if (i <= m){int size = m - i;for (int c = size; c < size; c++){data[k++] = data[i++];}}if (j <= n){int size = n - j;for (int c = size; c < size; c++){data[k++] = data[j++];}}
}void MSort(int* data, int s, int t) {if (s == t){}
}

测试3轮65536个随机整数数据，上述8中排序算法的时间对比：

快速排序是冒泡排序的1000倍。

工程项目地址：https://github.com/satadriver/dataStruct