工程建设项目网站,医院网站开发多少钱,东莞商贸公司寮步网站建设价格,现在网站建设用什么软件排序算法复习
冒泡排序
链接#xff1a;https://www.runoob.com/w3cnote/bubble-sort.html 每次循环对比【相邻】两个元素#xff0c;将最大的元素放到数组最后
void bubbleSort(int* arr, int n){//每次确认一个元素的最终位置#xff0c;循环n-1次即可确认全部元素的最…排序算法复习
冒泡排序
链接https://www.runoob.com/w3cnote/bubble-sort.html 每次循环对比【相邻】两个元素将最大的元素放到数组最后
void bubbleSort(int* arr, int n){//每次确认一个元素的最终位置循环n-1次即可确认全部元素的最终位置//外层只是用来控制循环次数并没有参与比较for(int i 0; i n - 1; i){//每次确认的元素都会被放在数组最后所以要循环遍历前面的元素//循环i次时确认了i1个元素的位置还剩下n-(i1)个元素的位置待确认所以内部循环n-i-1次for(int j 0; j n - i - 1; j){if(arr[j] arr[j 1]){ //升序排序所以用大于号swap(arr[j], arr[j 1]);}}}
}选择排序
链接https://www.runoob.com/w3cnote/selection-sort.html 每次循环对比i和j位置的元素不一定相邻不断交换i和j位置的元素将最小的元素放在最前面
void selectionSort(int* arr, int n){//每次循环确认一个元素的最终位置//升序排序每次将未确定最终位置的元素中最小的放在最前面for(int i 0; i n - 1; i){//内层循环寻找小于当前i位置元素的最小值for(int j i 1; j n; j){if(arr[i] arr[j]){swap(arr[i], arr[j]);}}}
}插入排序
链接https://www.runoob.com/w3cnote/insertion-sort.html 每次循环就是将第i1个元素插入到已经排好序的i个元素中 对几乎已经排好序的序列进行排列时比较高效。
void insertionSort(int* arr, int n){for(int i 1; i n; i){int tmp arr[i]; //arr[i]是需要单独记录的因为随着插入排序的进行原来i位置的元素会改变int j;for(j i; j 0; j--){if(arr[j - 1] tmp) arr[j] arr[j - 1];else{break;}}arr[j] tmp;}
}希尔排序 / 缩小增量排序
链接https://www.runoob.com/w3cnote/shell-sort.html 插入排序的升级版先将整个待排序的序列分割成若干个子序列分别进行直接插入排序待整个序列中的记录基本有序时再依次对全体数据进行直接插入排序
void shellSort(int* arr, int n){int h 1; //增量while(h n / 3){h h * 3 1;}while(h 1){//外层只是用来控制循环次数没有参与比较for(int i h; i n; i){for(int j i; j h; j - h){if(arr[j] arr[j - h]){swap(arr[j], arr[j - h]);}}}h / 3; //缩小增量}
}归并排序
链接https://blog.csdn.net/yang_yi520/article/details/125001902 分治思想先解决小问题再解决大问题
void merge(int* arr, int left, int mid, int right, int* temp){int i left;int j mid 1;int cur 0;while(i mid j right){if(arr[i] arr[j]){temp[cur] arr[i];}else{temp[cur] arr[j];}}while(i mid){temp[cur] arr[i];}while(j right){temp[cur] arr[j];}int n right - left 1;for(int i 0; i n; i){arr[left i] temp[i];}
}void mergeSort(int* arr, int left, int right, int* temp){if(left right){int mid left ((right - left) 1);mergeSort(arr, left, mid, temp); //先排 left-mid 位置的元素mergeSort(arr, mid 1, right, temp); //再排 mid1-right 位置的元素merge(arr, left, mid, right, temp); //将排好序的两边归并}
}快速排序
链接https://blog.csdn.net/weixin_45031801/article/details/126962679 分治先解决大问题再解决小问题
int part(int* arr, int left, int right){int pivot arr[left];int i left;int j right;while(i j){while(i j arr[j] pivot){j--;}if(i j) swap(arr[i], arr[j]);while(i j arr[i] pivot){i;}if(i j) swap(arr[i], arr[j--]);}return i;
}void quickSort(int* arr, int left, int right){if(left right){int mid part(arr, left, right);quickSort(arr, left, mid - 1); //mid-1quickSort(arr, mid 1, right); //mid1}
}堆排序
视频教程
//堆是一个完全二叉树//n: 堆中元素数量
//i: 要维护的元素
void heapify(int* arr, int n, int i) {int largest i; //先假定当前父子节点三个元素中最大值在父节点所在位置int lson i * 2 1; //左孩子下标int rson i * 2 2; //右孩子下标//要记得判断孩子下标是否超出范围if (lson n arr[largest] arr[lson])largest lson;if (rson n arr[largest] arr[rson])largest rson;if (largest ! i) {swap(arr[largest], arr[i]);heapify(arr, n, largest); //交换完元素后要继续维持堆的秩序}
}void heapSort(int* arr, int n) {//建堆//n/2-1 是堆中最后一个拥有子节点的父节点的下标for (int i n / 2 - 1; i 0; i--) {heapify(arr, n, i);}//排序for (int i n - 1; i 0; i--) {swap(arr[i], arr[0]); //将堆中最大的元素放到最后heapify(arr, i, 0); //确定最大元素的位置后剩余i个元素从位置0开始维持堆的秩序}
}计数排序
视频教程
//计数排序只能用于正数排序
void countSort(int* arr, int n) {//找到最大值以构造累计数组int max 0;for (int i 0; i n; i) {max max arr[i] ? max : arr[i];}//构造累计数组vectorint count(max 1, 0); //计数数组for (int i 0; i n; i) {count[arr[i]];}//将计数数组转为累计数组for (int i 1; i count.size(); i) {count[i] count[i - 1];}//计算最终排序vectorint temp(n, 0);for (int i 0; i n; i) {int index count[arr[i]] - 1;temp[index] arr[i];count[arr[i]]--;}for (int i 0; i n; i) {arr[i] temp[i];}
}桶排序
链接https://zhuanlan.zhihu.com/p/164992268
void bucketSort(int* arr, int n) {vectorvectorint bucket(5, vectorint());for (int i 0; i n; i) {bucket[arr[i] / 5].push_back(arr[i]);}for (int i 0; i 5; i) {sort(bucket[i].begin(), bucket[i].end());}int cur 0;for (int i 0; i 5; i) {for (int j 0; j bucket[i].size(); j) {arr[cur] bucket[i][j];}}
}基数排序
视频教程
void radixSort(int* arr, int n, int digit) {vectorint record(n);vectorint count(10);for (int i 0; i digit; i) {int division pow(10, i);for (int j 0; j n; j) {int num arr[j] / division % 10;count[num];}for (int j 1; j 10; j) {count[j] count[j - 1];}for (int j n - 1; j 0; j--) {int num arr[j] / division % 10;record[--count[num]] arr[j];}for (int j 0; j n; j) {arr[j] record[j];}count.assign(10, 0);}
}int main() {int arr[10] { 223, 124, 90, 8, 1128, 67, 980, 123, 90, 78 };int digit 0;//确定变量中最大位数for (int i 0; i 10; i) {int count 0;int tmp arr[i];while (tmp) {tmp / 10;count;}digit digit count ? digit : count;}radixSort(arr, 10, digit);for (int i 0; i 10; i) {cout arr[i] ;}cout endl;
}
