网站后台用什么开发,最近的战争新闻大事,北京装修公司电话名单,wordpress用户名备注文章目录一:简单选择排序算法1:思想(1):概念(2):举例验证(3):上码(3):时间复杂度和稳定性二:堆排序1:什么是堆2:堆排序的原理#xff08;以升序序列为例#xff09;3:堆排序算法的具体过程(1):先将无序序列建成一个堆(2):调换堆顶元素后,再调整剩下的元素为一个新的堆4:上码(… 文章目录一:简单选择排序算法1:思想(1):概念(2):举例验证(3):上码(3):时间复杂度和稳定性二:堆排序1:什么是堆2:堆排序的原理以升序序列为例3:堆排序算法的具体过程(1):先将无序序列建成一个堆(2):调换堆顶元素后,再调整剩下的元素为一个新的堆4:上码(1):heapSort函数(2):adjustHeap函数(调整数组为大顶堆)一:简单选择排序算法
1:思想
(1):概念
总共有n个数,同时下标是从0到n-1;我们要进行n-1趟的交换每一趟在 (n-i)-1个记录中寻找出最小值(也就是找出该数组下标后面数中的最小值)与i下标所代表的值进行比较,如果比其小那么就进行交换前提我们是求得是升序)。
(2):举例验证
文字验证 第一次从 arr[1]~arr[n-1]中选取最小值与 arr[0]作比较 判断是否交换
第二次从 arr[2]~arr[n-1]中选取最小值与 arr[1]作比较 判断是否交换
第三次从 arr[3]~arr[n-1]中选取最小值与 arr[2]作比较 判断是否交换
第 i 次从 arr[i]~arr[n-1]中选取最小值与 arr[i-1]作比较 判断是否交换
第 n-1 次从 arr[n-1]~arr[n-1]中选取最小值与 arr[n-2]作比较 判断是否交换
总共是要进行n-1轮 实例验证
原始数组: 4 3 5 1
第一轮排序: 1 3 2 4
第二轮排序: 1 3 5 4
第三轮排序: 1 3 4 5说明:
1.总共进行n-1轮排序
2.每一轮排序又是新的循环循环得规则是2.1:我们先假定当前数是最小的,并记录
(3):上码
public static void simpleSort(int [] arr) {for (int i 0; i arr.length-1; i) {//表示轮数int min arr[i];int minIndex i;for (int j i1; j arr.length; j) {//寻找i后面数的最小值if (arr[j] min) {min arr[j];minIndex j;}}if (i ! minIndex) {//交换当前下标i代表的数和求出的arr[minIndex] arr[i];arr[i] min;}}}(3):时间复杂度和稳定性
O(n^2)不稳定
二:堆排序
1:什么是堆
堆是具有下列性质的完全二叉树,每个结点的值都大于或等于其左右结点的的值,称为大顶堆;
每个结点值都小于等于其左右节点的值称为小顶堆。
2:堆排序的原理以升序序列为例
首先将无序序列中n个元素构造成一个大顶堆此时整个序列的最大值就是根节点然后将根节点和和数组中的末尾元素进行交换那么此时最后的元素就是最大值然后再将剩余的的n-1个元素重新进行调整然后构造成一个大顶堆如此反复进行我们最终就会得到一个有序序列了
3:堆排序算法的具体过程
(1):先将无序序列建成一个堆
for(int i arr.length/2-1; i 0; i--) {//这里的arr.length/2-1,是求出adjustHeap(arr,i,arr.length); //完全二叉树中最后一个非叶节点的下标。
}(2):调换堆顶元素后,再调整剩下的元素为一个新的堆
for(int i arr.length-1; i 0; i--) {//交换跟根节点和数组最后的元素的值这里最后的值是不断往前的int temp arr[0];arr[0] arr[i];arr[i] temp; //调整n-i个元素为一个大顶堆 adjustHeap(arr,0,i-1);
}
4:上码
(1):heapSort函数
//heapSort函数 (调整无序序列为大顶堆;将堆顶元素和数组最后的元素进行交换,然后将剩下的元素重新调整为大顶堆)
public static void heapSort1(int arr[]) {//调整无序序列为大顶堆;for (int i arr.length/2-1; i 0 ; i--) {adjustHeap(arr,i, arr.length-1);}//将堆顶元素和数组最后的元素进行交换,然后将剩下的元素重新调整为大顶堆经过n-1次循环我们将得到一个升序的序列for (int i arr.length-1; i 0 ; i--) {int temp arr[0];arr[0] arr[i];arr[i] temp;adjustHeap(arr,0,i-1);//从 根结点开始重新调整为大顶堆}
}(2):adjustHeap函数(调整数组为大顶堆)
//adjustHeap(向下调整)
public static void adjustHeap(int arr[],int index,int length) {//k 2 * index 1 表示的是左节点 k 2*index 2表示的是右结点for (int k 2*index1; k length ; k k * 2 1) {//比较该结点的左右孩子结点的值谁大if (k1 length arr[k] arr[k1]) k;//右结点值比较大if (arr[k] arr[index]) { //子结点的值比父节点值大的话int temp arr[index];//需要调整的根节点arr[index] arr[k];//那就孩子结点跟父节点进行交换arr[k] temp;index k;//更新index,将孩子结点作为新的根节点继续往下进行比较} else {break;}}
}
