三亚网站建设制作,平面设计速成班多少钱,高端网站开发注意事项,华阳路街道网站建设꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好#xff0c;我是xiaoxie.希望你看完之后,有不足之处请多多谅解#xff0c;让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN … ꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好我是xiaoxie.希望你看完之后,有不足之处请多多谅解让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如需转载还请通知˶⍤⃝˶个人主页xiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 系列专栏xiaoxie的JAVA系列专栏——CSDN博客●ᴗσσணღ*我的目标:团团等我( ◡̀_◡́ ҂) ( ⸝⸝⸝›ᴥ‹⸝⸝⸝ )欢迎各位→点赞 收藏⭐️ 留言关注互三必回! 一.排序的概念 排序的概念 排序 所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。 稳定性 假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持 不变即在原序列中 r[i]r[j] 且 r[i] 在 r[j] 之前而在排序后的序列中 r[i] 仍在 r[j] 之前则称这种排序算法是稳 定的否则称为不稳定的。 内部排序 数据元素全部放在内存中的排序。 外部排序 数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。 二.插入排序
1.直接插入排序 直接插入排序是一种简单的插入排序法其基本思想是 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到 一个新的有序序列 。实际中我们玩扑克牌时就用了插入排序的思想。 1.过程
假设我们有一个数组array{1587635982318210} 我们如果使用直接插入排序的过程如下
原始 15 87 63 5 98 23 1 82 10
第一趟 15 87 63 5 98 23 1 82 10
第二趟 15 87 63 5 98 23 1 82 10
第三趟15 63 87 5 98 23 1 82 10
......
第n(9)趟: 1 5 10 15 23 63 82 87 98
2.代码
我们可以把他写为Java代码如下
public class Sort {public static void insertSort(int[] array) {insert(array,0, array.length-1);}private static void insert(int[] array,int start,int end) {for (int i start1; i end; i) {int tmp array[i];int j i-1;for (;j start; j--) {if(array[j] tmp) {array[j1] array[j];}else {break;}}array[j1] tmp;}}
}
C版本如下
#include iostream
using namespace std;class Sort {
public:static void insertSort(int array[], int size) {insert(array, 0, size-1);}private:static void insert(int array[], int start, int end) {for (int i start1; i end; i) {int tmp array[i];int j i-1;for (; j start; j--) {if (array[j] tmp) {array[j1] array[j];} else {break;}}array[j1] tmp;}}
};
3.时间复杂度
最好情况下
直接插入排序在最好情况下也就是在数据都有序的情况下为On)。
最坏情况下
直接插入排序的最坏情况也就是在数据为逆序的情况下为On^2)。
4.空间复杂度
因为直接插入排序是在本数组中实现的没有借用辅助空间所以为O1。
5.稳定性
该算法为稳定的
值得注意的是元素集合越接近有序直接插入排序算法的时间效率越高。
2. 希尔排序( 缩小增量排序 ) 希尔排序法又称缩小增量法。希尔排序法的基本思想是 将待排序的数组按照一定的增量分组对每个分组进行直接插入排序然后逐步缩小增量重复进行分组和直接插入排序的操作直到增量缩小为1最后进行最后一次直接插入排序。 1.过程 2.代码
java
public class Sort {public static void shellSort(int[] array) {int gap array.length;while (gap 1) {gap / 2;Shell(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[jgap] array[j];}else {break;}}array[jgap] tmp;}}
}C
#include iostream
using namespace std;void shellSort(int array[], int size) {int gap size;while (gap 1) {gap / 2;Shell(array, size, gap);}
}void Shell(int array[], int size, int gap) {for (int i gap; i size; 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;}
} 3.时间复杂度 希尔排序的时间复杂度不好计算因为 gap 的取值方法很多导致很难去计算因此在不同的书中给出的希尔排序的时间复杂度都不固定 《数据结构 (C 语言版 ) 》 --- 严蔚敏 《数据结构-用面向对象方法与C描述》--- 殷人昆 4.空间复杂度
因为希尔排序是直接插入排序的优化所以是在本数组中实现的没有借用辅助空间所以为O1。
5.稳定性
不稳定
6.希尔排序的特性 1. 希尔排序是对直接插入排序的优化。 2. 当 gap 1 时都是预排序目的是让数组更接近于有序。当 gap 1 时数组已经接近有序的了这样就会很快。这样整体而言可以达到优化的效果。 三.选择排序
3.直接选择排序 每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 。 1.过程 1.在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素 2.若它不是这组元素中的最后一个(第一个)元素则将它与这组元素中的最后一个第一个元素交换 3.在剩余的array[i]--array[n-2]array[i1]--array[n-1]集合中重复上述步骤直到集合剩余1个元素 2.代码
Java
public class Sort {public static void selectSort(int[] array) {select(array,0, array.length-1);}private static void select(int[] array,int start,int end) {for (int i 0; i end ; i) {int minIndex i;for (int j i1; j end ; j) {if(array[j] array[minIndex]) {minIndex j;}}swap(array,i,minIndex);}}private static void swap(int[]array,int i,int j) {int tmp array[i];array[i] array[j];array[j] tmp;}
}
C #include iostream
using namespace std;
void selectSort(int array[], int size) {select(array, 0, size - 1);
}void select(int array[], int start, int end) {for (int i 0; i end; i) {int minIndex i;for (int j i 1; j end; j) {if (array[j] array[minIndex]) {minIndex j;}}swap(array, i, minIndex);}
}void swap(int array[], int i, int j) {int tmp array[i];array[i] array[j];array[j] tmp;
}3.时间复杂度 最好情况和最坏情况都为On^2 所以不是很推荐使用 4.空间复杂度 因为直接选择排序是在本数组中实现的没有借用辅助空间所以为O1。 5.稳定性 不稳定 直接选择排序思考非常好理解但是效率不是很好。实际中很少使用 4.堆排序需要重点掌握 堆排序 (Heapsort) 是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。它是通过堆来进行选择数据。 需要注意的是排升序要建大堆排降序建小堆 。 1.过程 2.代码
Java
private static void swap(int[]array,int i,int j) {int tmp array[i];array[i] array[j];array[j] tmp;}public static void heapSort(int[] array) {crateHeap(array);//首先创建大根堆int end array.length-1;while (end 0) {swap(array,0,end);siftDown(array,0,end);end--;}}// 创建大根堆private static void crateHeap(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*parent1;while (child len) {if(child1 len array[child] array[child1]) {child;}if(array[child] array[parent]) {swap(array,child,parent);parent child;child 2*parent1;}else {break;}}}
C
#include iostream
using namespace std;void swap(int array[], int i, int j) {int tmp array[i];array[i] array[j];array[j] tmp;
}void heapSort(int array[], int length) {createHeap(array, length); // 首先创建大根堆int end length - 1;while (end 0) {swap(array, 0, end);siftDown(array, 0, end);end--;}
}// 创建大根堆
void createHeap(int array[], int length) {for (int parent (length - 2) / 2; parent 0; parent--) {siftDown(array, parent, length);}
}// 向下调整
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;}if (array[child] array[parent]) {swap(array, child, parent);parent child;child 2 * parent 1;} else {break;}}
}3.时间复杂度 因为堆是一颗完全二叉树所以他的时间复杂度为On*logN)。
4.空间复杂度
没有借助辅助空间所以空间复杂度为O(1)。
5.稳定性
不稳定
四.交换排序 基本思想所谓交换就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置交换排序的特点是 将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动 5.冒泡排序
1.过程 2.代码
Java private static void swap(int[]array,int i,int j) {int tmp array[i];array[i] array[j];array[j] tmp;}public static void bubbleSort(int[] array) {//10个元素遍历9趟for (int i 0; i array.length-1; i) {boolean flag false;for (int j 0; j array.length-1-i; j) {if(array[j] array[j1]) {swap(array,j,j1);flag true;}}//没有交换就证明有序if(flag false) {return;}}}
C
#include iostream
using namespace std;void swap(int array[], int i, int j) {int tmp array[i];array[i] array[j];array[j] tmp;
}void bubbleSort(int array[], int length) {// 对于10个元素遍历9趟for (int i 0; i length - 1; i) {bool flag false;for (int j 0; j length - 1 - i; j) {if (array[j] array[j 1]) {swap(array, j, j 1);flag true;}}// 若没有交换发生则证明数组已有序if (!flag) {return;}}
}
3.时间复杂度
最好情况下
冒泡排序在最好情况下也就是在数据都有序的情况下为On)。
最坏情况下
冒泡排序的最坏情况也就是在数据为逆序的情况下为On^2)。
4.空间复杂度
没有借助辅助空间所以空间复杂度为O(1)。
5.稳定性
稳定
6.快速排序重点掌握 快速排序是 Hoare 于 1962 年提出的一种二叉树结构的交换排序方法其基本思想为 任取待排序元素序列中的某元 素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有 元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止 。 因为根据划分基准值的方法不同其过程也不一样一般有Hoare法挖坑法常用来划分基准值 1.1Hoare法过程 需要注意的是快速排序需要进行优化防止出现像{123456789}这样的情况如果出现这种情况二叉树会变成一颗斜树降低排序速率这时候我们需要使用1 .三数取中法选基准值 如果 . 递归到小的子区间时可以考虑使用插入排序 这里就不优化了感兴趣的可以自己下去实现 1.2Hoare法代码 private static void swap(int[]array,int i,int j) {int tmp array[i];array[i] array[j];array[j] tmp;}public static void quickSort(int[] array) {quick(array,0, array.length-1);}private static void quick(int[] array,int left,int right) {if(right-left 1) {return;}//三数取中法int index middleNum(array,left,right);swap(array,left,index);int pivot partitionHoare(array,left,right);quick(array,left,pivot-1);//递归左边quick(array,pivot1,right);//递归右边}//三数取中private static int middleNum(int[] array,int start,int end) {int mid start((end-start)1);if(array[start] array[end]) {if(array[mid] array[end]) {return end;} else if (array[mid] array[start]) {return start;}else {return mid;}}else {if(array[mid] array[end]) {return end;} else if (array[mid] array[start]) {return start;}else {return mid;}}}//获取基准值的位置使用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,left,i);return left;}
C版本
#include iostream
using namespace std;void swap(int array[], int i, int j) {int tmp array[i];array[i] array[j];array[j] tmp;
}void quickSort(int array[], int length) {quick(array, 0, length - 1);
}void quick(int array[], int left, int right) {if (right - left 1) {return;}// 三数取中法int index middleNum(array, left, right);swap(array, left, index);int pivot partitionHoare(array, left, right);quick(array, left, pivot - 1); // 递归左边quick(array, pivot 1, right); // 递归右边
}// 三数取中
int middleNum(int array[], int start, int end) {int mid start ((end - start) 1);if (array[start] array[end]) {if (array[mid] array[end]) {return end;} else if (array[mid] array[start]) {return start;} else {return mid;}} else {if (array[mid] array[end]) {return end;} else if (array[mid] array[start]) {return start;} else {return mid;}}
}// 获取基准值的位置使用Hoare法
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, left, i);return left;
}
2.1挖坑法过程重点掌握考试选择题过程一般使用挖坑法 2.2 挖坑法代码重点掌握
Java private static void swap(int[]array,int i,int j) {int tmp array[i];array[i] array[j];array[j] tmp;}public static void quickSort(int[] array) {quick(array,0, array.length-1);}private static void quick(int[] array,int left,int right) {if(right-left 1) {return;}//三数取中法int index middleNum(array,left,right);swap(array,left,index);int pivot partition(array,left,right);quick(array,left,pivot-1);//递归左边quick(array,pivot1,right);//递归右边}//三数取中private static int middleNum(int[] array,int start,int end) {int mid start((end-start)1);if(array[start] array[end]) {if(array[mid] array[end]) {return end;} else if (array[mid] array[start]) {return start;}else {return mid;}}else {if(array[mid] array[end]) {return end;} else if (array[mid] array[start]) {return start;}else {return mid;}}}//获取基准值的位置使用挖坑法private static int partition(int[] array,int left ,int right) {int tmp array[left];//记录基准值while (left right) {while (left right array[right] tmp) {right--;}array[left] array[right];while (left right array[left] tmp) {left;}array[right] array[left];}array[left] tmp;// 将基准值放入正确位置return left;}
C
#include iostream
using namespace std;void swap(int array[], int i, int j) {int tmp array[i];array[i] array[j];array[j] tmp;
}void quickSort(int array[], int length) {quick(array, 0, length - 1);
}void quick(int array[], int left, int right) {if (right - left 1) {return;}// 三数取中法int index middleNum(array, left, right);swap(array, left, index);int pivot partition(array, left, right);quick(array, left, pivot - 1); // 递归左边quick(array, pivot 1, right); // 递归右边
}// 三数取中
int middleNum(int array[], int start, int end) {int mid start ((end - start) 1);if (array[start] array[end]) {if (array[mid] array[end]) {return end;} else if (array[mid] array[start]) {return start;} else {return mid;}} else {if (array[mid] array[end]) {return end;} else if (array[mid] array[start]) {return start;} else {return mid;}}
}// 获取基准值的位置使用挖坑法
int partition(int array[], int left, int right) {int pivot array[left]; // 基准值while (left right) {while (left right array[right] pivot) {right--;}array[left] array[right];while (left right array[left] pivot) {left;}array[right] array[left];}array[left] pivot; // 将基准值放入正确位置return left;
}
3.时间复杂度
最好情况下数据为无序的时候为O(n*logN)。
最坏情况下数据为有序或者是逆序的时候为On^2。
4.空间复杂度
在递归调用过程中需要使用O(log n)的栈空间来存储递归调用的上下文信息所以空间复杂度为O(logN)。
5.稳定性
不稳定
7.归并排序重点掌握 归并排序 MERGE-SORT 是建立在归并操作上的一种有效的排序算法 , 该算法是采用分治法 Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使 子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 1.过程 2.代码
Java
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,right,mid);}private static void merge(int[] array,int left,int right,int mid) {int s1 left;int e1 mid;int s2 mid1;int e2 right;int[] tmp new int[right-left1];//创建一个临时数组来储存数据int k 0;//临时数组下标while (s1 e1 s2 e2) {if(array[s1] array[s2]) {tmp[k] array[s1];}else {tmp[k] array[s2];}}//看那个数组还有数据就拷贝过去while (s1 e1) {tmp[k] array[s1];}while (s2 e2) {tmp[k] array[s2];}//3.拷贝到源数组for (int i 0; i k; i) {array[ileft] tmp[i];}}
C
#include iostream
using namespace std;void mergeSort(int array[], int length) {mergeFunc(array, 0, length - 1);
}void mergeFunc(int array[], int left, int right) {if (left right) {return;}int mid left ((right - left) 1);// 开始分解mergeFunc(array, left, mid);mergeFunc(array, mid 1, right);// 开始合并merge(array, left, right, mid);
}void merge(int array[], int left, int right, int mid) {int s1 left;int e1 mid;int s2 mid 1;int e2 right;int tmp[right - left 1]; // 创建一个临时数组来储存数据int k 0; // 临时数组下标while (s1 e1 s2 e2) {if (array[s1] array[s2]) {tmp[k] array[s1];} else {tmp[k] array[s2];}}// 看那个数组还有数据就拷贝过去while (s1 e1) {tmp[k] array[s1];}while (s2 e2) {tmp[k] array[s2];}// 3.拷贝到源数组for (int i 0; i k; i) {array[i left] tmp[i];}
} 3.时间复杂度
时间复杂度为O(n*logN)。
4.空间复杂度
因为需要借助临时数组所以空间复杂度为On。
5.稳定性
稳定
五.各个排序算法的时间复杂度和空间复杂度以及稳定性总结 以上就是关于基于比较排序的所以的内容了如果有帮助到你创作不易希望可以给博主一个关注感谢你的阅读希望能够对你有所帮助
