四川高速公路建设开发总公司网站,网站建设零基础好学吗,个人适合做的网站,wordpress本地做好了怎么备份常见排序算法--Java实现插入排序直接插入排序折半插入排序希尔排序交换排序冒泡排序快速排序选择排序直接选择排序堆排序归并排序基数排序各种排序方法比较在网上找了些排序算法的资料。此篇笔记本人总结比较#xff0c;简单注释#xff0c;觉得比较好理解#xff0c;且相对…
常见排序算法--Java实现插入排序直接插入排序折半插入排序希尔排序交换排序冒泡排序快速排序选择排序直接选择排序堆排序归并排序基数排序各种排序方法比较在网上找了些排序算法的资料。此篇笔记本人总结比较简单注释觉得比较好理解且相对简短方便记忆。插入排序
直接插入排序
默认第0个有序后面挨个插入前面有序的数中(像打扑克插牌一样)
/***直接插入排序* 默认第0个有序后面挨个插入前面有序的数中(像打扑克插牌一样)*/
public static void ChaRu(int a[], int n){int i,j;// 第0个有序从第1个开始for(i 1; i n; i){int temp a[i]; // 要插入的元素保存起来// 在前面i-1个有序数组中找插入的下标for(j i - 1; j 0 temp a[j]; j--){a[j 1] a[j]; // 移动覆盖}a[j 1] temp; // 找到位置了插入继续把后面的插入循环}
}折半插入排序
折半插入排序增加二分查找
/*** 折半插入排序增加二分查找*/
public static void ZheBanCha(int a[], int n){int i, j;for(i 1; i n; i){int temp a[i]; // 待插入的元素// 二分查找法找插入的位置int left 0, right i - 1; // 0开始while(left right){int mid (left right) / 2;if(temp a[mid]) right mid - 1;else left mid 1;} // right 1 为插入的位置// 统一后移元素空出插入位置for(j i - 1; j right 1; j--){ // a[j 1] a[j];}a[right 1] temp; // right 1 插入}
}希尔排序
希尔排序新增for循环步长为有序增量表:421[把1变成d]
/*** 希尔排序新增for循环步长为有序增量表:421[把1变成d]*/
public static void shell(int[] a, int n) {int d, i, j;// 步长变化每次减半直到为1for(d n / 2; d 1; d d / 2){ // 新增for步骤for(i d; i n; i){ // 1 - dint temp a[i];for(j i - d; j 0 temp a[j]; j - d){a[j d] a[j];}a[j d] temp;}}
}交换排序
冒泡排序
每一趟都会把最大的数排到最后然后继续看前面的不管最后的了(因为后面有序了)
/*** 冒泡排序加了flag优化* 每一趟都会把最大的数排到最后然后继续看前面的不管最后的了(因为后面有序了)*/
public static void MaoPao(int[] a, int n) {for(int i 0; i n; i){ // i趟数boolean flag false; // 提前退出冒泡循环的标志位for(int j 0; j n - i - 1; j){if(a[j] a[j1]){ // 比后面大就交换int temp a[j];a[j] a[j1];a[j1] temp;flag true; // 表示有数据交换}}if(flag false) return; // 本趟没有数据交换提前退出}
}快速排序
快速排序递归轴划分左右{ 轴元素放到最终位置[比轴小轴比轴大] }与其他排序算法相反的是元素越有序快排时间复杂度越高
/*** 快速排序递归轴划分左右{轴元素放到最终位置[比轴小轴比轴大]}* 与其他排序算法相反的是元素越有序快排时间复杂度越高*/
public static void QuickSort(int[] a, int low, int high) {if(low high) { // 递归跳出的条件int pivot patition(a, low, high); // 划分函数QuickSort(a, low, pivot - 1); // 划分左子表QuickSort(a, pivot 1, high); // 划分右子表}
}// 用第一个元素将待排序列划分为左右两个部分比轴小比轴大
public static int patition(int[] a, int low, int high) {int pivot a[low]; // (暂存)第一个元素作为轴while(low high) { // 用low,high寻找轴的最终位置while(low high a[high] pivot) high--;a[low] a[high]; // 比轴小的移到左端while(low high a[low] pivot) low;a[high] a[low]; // 比轴大的移到右端}a[low] pivot; // 轴元素放到最终位置*return low; // 返回存放轴的最终位置
}选择排序
直接选择排序
简单选择排序每趟选一个最小的元素交换到前面
/*** 简单选择排序每趟选一个最小的元素交换到前面*/
public static void JianDanXuanZe(int[] a, int n) {for(int i 0; i n -1; i){ // 总共n-1趟最后一次就不用了int min i; // 记录此趟最小元素位置for(int j i 1; j n; j) { // 再a[i..n-1]中选择最小元素if(a[j] a[min]) min j; // 更新最小元素位置}if(min ! i) { // 交换把最小值放到i的位置int temp a[i];a[i] a[min];a[min] temp;}}
}堆排序
/*** 堆排序(从小到大)*/
public static void heapSortAsc(int[] a, int n) {int i,tmp;// 从(n/2-1) -- 0逐次遍历。遍历之后得到的数组实际上是一个(最大)二叉堆。for (i n / 2 - 1; i 0; i--)maxHeapDown(a, i, n-1);// 从最后一个元素开始对序列进行调整不断的缩小调整的范围直到第一个元素for (i n - 1; i 0; i--) {// 交换a[0]和a[i]。交换后a[i]是a[0...i]中最大的。tmp a[0];a[0] a[i];a[i] tmp;// 调整a[0...i-1]使得a[0...i-1]仍然是一个最大堆。// 即保证a[i-1]是a[0...i-1]中的最大值。maxHeapDown(a, 0, i-1);}
}/*** (最大)堆的向下调整算法** 注: 数组实现的堆中第N个节点的左孩子的索引值是(2N1)右孩子的索引是(2N2)。* 其中N为数组下标索引值如数组中第1个数对应的N为0。** 参数说明:* a -- 待排序的数组* start -- 被下调节点的起始位置(一般为0表示从第1个开始)* end -- 截至范围(一般为数组中最后一个元素的索引)*/
public static void maxHeapDown(int[] a, int start, int end) {int c start; // 当前(current)节点的位置int l 2*c 1; // 左(left)孩子的位置int tmp a[c]; // 当前(current)节点的大小for (; l end; cl,l2*l1) {// l是左孩子l1是右孩子if ( l end a[l] a[l1])l; // 左右两孩子中选择较大者即m_heap[l1]if (tmp a[l])break; // 调整结束else { // 交换值a[c] a[l];a[l] tmp;}}
}归并排序
归并排序辅助数组递归分治合并
/*** 归并排序辅助数组递归分治合并*/
int[] tmp new int[a.length]; // 新建一个临时数组存放*public static void mergeSort(int[] a, int low, int high, int[] tmp) {if(low high){int mid (low high) / 2; // 从中间划分mergeSort(a, low, mid, tmp); // 对左半部分归并排序mergeSort(a, mid 1, high, tmp); // 对右边部分归并排序// 上面两步递归一直划分到每个子序列只含有一个元素merge(a, low, mid, high, tmp); // 合并两个有序序列归并}
}// a[low..mid] 和 a[mid1..high] 将两个部分归并合并
public static void merge(int[] a, int low, int mid, int high, int[] tmp) {int i, j, k;// 将a[] 中所有元素复制到 tmp[]辅助数组for(k low; k high; k) {tmp[k] a[k];}// 两个区间两个指针 i,j比较将较小值复制到 a[]中for(i low, j mid 1, k i; i mid j high; k){if(tmp[i] tmp[j])a[k] tmp[i];elsea[k] tmp[j];}// 若左右序列还有剩余则将其全部拷贝进 a[]中while(i mid) a[k] tmp[i];while(j high) a[k] tmp[j];
} 基数排序
基数排序(分配收集)
*** 基数排序(分配收集)* 个位分配收集十位分配收集...*/
public static void radixSort(int[] a){int exp; // 指数。当对数组按各位进行排序时exp1按十位进行排序时exp10// 获取数组a中最大值int max a[0];for(int i 1; i a.length; i){if(a[i] max) max a[i];}// 从个位开始对数组a按指数进行排序个位十位百位。。。for(exp 1; max / exp 0; exp * 10){int[] output new int[a.length]; // 存储被排序数据的临时数组int[] buckets new int[10]; // 桶 0-9// 将数据出现的次数存储在buckets[]中for(int i 0; i a.length; i){buckets[(a[i] / exp) % 10];}// 更改buckets[i]。目的是让更改后的buckets[i]的值是该数据在output[]中的位置。for(int i 1; i 10; i){buckets[i] buckets[i - 1];}// 将数据存储到临时数组output[]中for(int i a.length - 1; i 0; i--){output[buckets[(a[i] / exp) % 10] - 1] a[i];buckets[(a[i] / exp) % 10]--;}// 将排序好的数据赋值给a[]for (int i 0; i a.length; i) {a[i] output[i];}}
}各种排序方法比较 引用 代码后面附的总结PPT为王道数据结构课件截图 排序方法比较图片为青岛大学王卓老师的数据结构课件截图
