城市建设最好的网站,查询网站whois,百度搜题,莱芜东风街F B I W a r n i n g : \color{red}FBI \qquad Warning: FBIWarning:
本人没有完整的计算机科班的教育经历#xff0c;但是一直在兢兢业业#xff0c;努力学习。
这些排序函数都是自己零零散散写的#xff0c;也没有经过深思熟虑和优化#xff0c;纯粹是为了自娱自乐。
… F B I W a r n i n g : \color{red}FBI \qquad Warning: FBIWarning:
本人没有完整的计算机科班的教育经历但是一直在兢兢业业努力学习。
这些排序函数都是自己零零散散写的也没有经过深思熟虑和优化纯粹是为了自娱自乐。
冒泡排序
代码里有两种实现方式感觉第二种比较正宗第一种跟插入排序相似度很高。
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;
}插入排序
此处可以看出插入排序和冒泡排序还是有很大的不同。
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;
}选择排序
按照次序每次挑选一个最小的放到相应的次序位置。
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;
}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]);}
}二分插入排序
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;}
}快速排序
快速排序一种是本人自己写的一种是算法书上的源码。
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;
}堆排序 堆排序是我最喜欢的一种排序。有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);}
}归并排序
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
