做国际网站花钱吗,企业门户网站数据库设计,沈阳市建设工程信息网,网站建设硬件设置排序
排序的概念
所谓排序 #xff0c;就是让一串记录#xff0c;按照其中某些或者某个关键字的大小#xff0c;递增或递减的排列起来的操作。 稳定性#xff1a;就比如在待排序的序列中#xff0c;存在多个具有相同关键字的记录 #xff0c;如果经过排序这些相同的关键…排序
排序的概念
所谓排序 就是让一串记录按照其中某些或者某个关键字的大小递增或递减的排列起来的操作。 稳定性就比如在待排序的序列中存在多个具有相同关键字的记录 如果经过排序这些相同的关键字相对位置还是不变则称这种排序是稳定的否则就是不稳定的。下面用图例来解析一下 排序还分为内部排序和外部排序 内部排序 数据元素全部在内存中排序。 外部排序 数据元素大多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。
插入排序
插入排序
直接插入排序就是一种简单的插入排序法他就是把待排序的记录按照其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为一个新的有序序列。在实际生活中 我们玩扑克牌时就应用了插入排序的思想。
步骤 从第2个元素开始如果第一个元素比第二个元素大 那就得交换 一直往前遍历直到小于0下标 在待排序元素中假设前n-个元素已经有序 如果第n个元素比第n-1个元素大 那说明前n个已经有序 如果比他小就按照遍历一直找到比前面的数字大为止 找到就插入进去就行。 因为我们不能够确定待排序中哪一部分是有序的 所以我们从第二个元素开始遍历 默认第一个元素是有序的 再依次遍历后面的元素 再慢慢插入进来 变成一个新的有序序列。 下面让我们用动图演示一遍 代码实现如下 //插入排序public static void insertSort(int[] array) {for (int i 1; i array.length; i) {//要定义一个变量存一下i下标的值int tmp array[i];int j i - 1;for (; j 0; j--) {if (array[j] tmp) {array[j 1] array[j];} else {break;}}array[j 1] tmp;}}时间复杂度最好情况下待排序列是升序的为O(N);最坏情况下待排序列是逆序的为O(N2), 空间复杂度O(1);而且插入排序是稳定的
希尔排序
希尔排序
希尔排序又称为缩小增量法。希尔排序法的基本思想是先给定一个整数gap把待排序文件中所有的记录分为多个组所有距离为gap的记录分为一组并对每一组的记录进行排序 然后重复上诉操作直到gap 1时 所有记录都排好序了 动图表示如下 代码如下
//希尔排序public static void shellSort(int[] array) {int gap array.length;while (gap 1) {gap gap / 2; //或者可以写成 gap gap / 3 1shell(array, gap);}}private static void shell(int[] array, int gap) {//每组的数据都在变化for (int i gap; i array.length; i) {int tmp array[i];int j i - gap;for (; j 0; j - gap) {if (array[j] tmp) {array[j gap] array[j];} else {break;}array[j gap] tmp;}}}
时间复杂度希尔排序的时间复杂度 是不好计算的 他会根据gap的取值的不同而不同。通过大量的实验现在时间复杂度只能在O(n1.25) ~O(1.6*n1.25)来计算。 空间复杂度O(1); 希尔排序是快速排序的优化 希尔排序是不稳定的。
选择排序
选择排序
选择排序的思想就是 每次遍历待待排序中的元素 选出最小值排到序列的起始位置 一直排 直到全部排完 比如说现在第一个元素是4 后面找完待排序如果有比4小的就换 没有就不换。 动图演示 代码表示如下 //选择排序public static void selectSort(int[] array) {for (int i 0; i array.length; i) {//定义一个临时变量把i下标存下来int minIndex i;int j i 1;for (; j array.length; j) {if (array[j] array[minIndex]) {minIndex j;}}swap(array, minIndex, i);}}时间复杂度最坏情况ON2,最好情况O(N2); 空间复杂度O(1) 选择排序不稳定
冒泡排序
冒泡排序 冒泡排序的思想 就是遍历和交换 如果左边的大于右边就交换 排下来 最大的就在右边了 。 具体情况看动图演示 代码实现如下
// 冒泡排序public static void bubbleSort(int[] array) {// write code herefor (int i 0;iarray.length;i){for (int j 0;j array.length-1-i;j){if (array[j]array[j1]){swap(array,j,j1);}}}}时间复杂度最坏情况下O(N2),最好情况下O(N) 空间复杂度O(1)
快速排序法
快速排序算法 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为任意取待排序元素序列中的某元素作为基准值按照该排序码将排序集合分割为两个子序列让左子序列中所有元素均小于基准值右子序列均大于基准值然后递归左和右 直到所有元素有序。
快排右可以分为两种方法去实现 Hoare法 和 挖坑法。
Hoare法
用最左边的值作为一个tmp定义一个left和rightleft从左往右走 right从右往左走 一定要right先走这样才能保证相遇时候的值是小于tmp的值。 在走的过程中如果right遇到比tmp小的值就停下来等left走直到left遇到一个比tmp大的数 left和right的值交换 right继续走 直到他们相遇将相遇的值和tmp交换。此时tmp的左边都是小于tmp的数 右边都是大于tmp的数。 动图演示 代码表示如下 //快速排序public static void quickSort(int[] array) {quick(array,0,array.length-1);//取闭区间}private static void quick(int[] array,int start,int end) {if (start end){return;}int pivot partitionHoare(array,start,end);quick(array,start,pivot-1);quick(array,pivot1,end);}//Hoare法private static int partitionHoare(int[] array,int left,int right) {int tmp array[left];//基准int i left;while (left right) {while (left right array[right] tmp) {right--;}while (left right array[left] tmp) {left;}swap(array,left,right);}//相遇了 换swap(array,i,left);return left;}挖坑法
挖坑法的思路和Hoare法差不多 就是选最左边或者最右边的数据作为一个坑也是定义两个指针在两边走 我们直接看动图演示 代码实现如下 //快速排序public static void quickSort(int[] array) {quick(array,0,array.length-1);//取闭区间}private static void quick(int[] array,int start,int end) {if (start end){return;}int pivot partition(array,start,end);quick(array,start,pivot-1);quick(array,pivot1,end);}
//挖坑法private static int partition(int[] array,int left,int right) {int tmp array[left];while (left right){while (left right array[right] tmp) {right--;}if (left right){break;}array[left] array[right];while (left right array[left] tmp) {left;}if (left right){break;}array[right] array[left];}array[left] tmp;return left;}还有非递归写法
//快速排序非递归实现public static void quickSortNor(int[] array) {StackInteger stack new Stack();int left 0;int right array.length-1;int pivot partition(array,left,right);if(pivot-1 left) {stack.push(left);stack.push(pivot-1);}if(pivot 1 right) {stack.push(pivot1);stack.push(right);}while (!stack.isEmpty()) {right stack.pop();left stack.pop();pivot partition(array,left,right);if(pivot-1 left) {stack.push(left);stack.push(pivot-1);}if(pivot 1 right) {stack.push(pivot1);stack.push(right);}}}归并排序
归并排序 归并排序和快速排序一样采用了分治的思想他就是将待排序的数组不断拆分直到拆到区间里只有一个元素为止然后开始合并 一层一层地合并 直到整个数组有序。这里很显然要用递归的方式去实现归并排序。 归并排序就是典型用空间换时间的一种排序。 动图演示 代码实现
//归并排序public static void mergeSort(int[] array) {mergeFunc(array,0,array.length-1);}private static void mergeFunc(int[] array,int left,int right) {if (left right) {return;}int mid left ((right - left) 1);mergeFunc(array,left,mid);mergeFunc(array,mid1,right);//左边分解完 右边分解完 开始合并merge(array,left,mid,right);}private static void merge(int[] array,int left,int mid,int right) {int s1 left;int e1 mid;int s2 mid1;int e2 right;int[] tmpArray new int[right-left1];int k 0;//得保证两个表都有数据while (s1 e1 s2 e2) {if (array[s1] array[s2]) {tmpArray[k] array[s1];}else {tmpArray[k] array[s2];}}//2.看还有哪个数组还有数据 直接加在数组后面while (s1 e1) {tmpArray[k] array[s1];}while (s2 e2) {tmpArray[k] array[s2];}//拷贝到原来的数组for (int i 0;i k;i) {array[ileft] tmpArray[i];}}时间复杂度ONlog2N 空间复杂度O(N) 归并排序稳定
堆排序
排序的思想首先得将待排序的数组构造成一个大根堆此时整个数组的最大值就是**堆结构的顶端。**然后将顶端的数将最后一个元素交换此时末尾为最大值待排序元素就剩n-1个了。然后再将剩下的n-1个元素调整为大根堆循环去执行此操作最后便可以得到有序的数组。 升序用大根堆 降序用小根堆。 图解 时间复杂度O(N*logN); 空间复杂度O(1); 堆排序不稳定 代码实现如下 //堆排序public static void heapSort(int[] array) {//创建大根堆createHeap(array);int end array.length - 1;while (end 0) {swap(array, 0, end);siftDown(array, 0, end);end--;}}private static void createHeap(int[] array) {for (int parent (array.length - 1 - 1) / 2; parent 0; parent--) {siftDown(array, parent, array.length);}}private static void siftDown(int[] array, int parent, int len) {int child (2 * parent) 1;while (child len) {if (child 1 len array[child] array[child 1]) {child child 1;}if (array[child] array[parent]) {swap(array, child, parent);parent child;child 2 * parent 1;} else {break;}}}private static void swap(int[] array, int i, int j) {int tmp array[j];array[j] array[i];array[i] tmp;}到这里就讲完了 数据结构7大排序 当然还有很多排序 如果有兴趣可以去查找一下资料 比如说 基数排序 计数排序 桶排序
