网站制作的基本概念,wordpress有一个100的缩略图,网站要怎样建设,开源企业网站源码1. 插入排序 原理#xff1a;遍历到第N个元素的时候前面的N-1个元素已经是排序好的了#xff0c;那么就查找前面的N-1个元素把这第N个元素放在合适的位置#xff0c;如此下去直到遍历完序列的元素为止。 算法的复杂度也是简单的#xff0c;排序第一个需要1的复杂度…1. 插入排序 原理遍历到第N个元素的时候前面的N-1个元素已经是排序好的了那么就查找前面的N-1个元素把这第N个元素放在合适的位置如此下去直到遍历完序列的元素为止。 算法的复杂度也是简单的排序第一个需要1的复杂度排序第二个需要2的复杂度因此整个的复杂度就是 1 2 3 …… N ON ^ 2的复杂度。 // 插入排序
void InsertSort(int array[], int length)
{int i, j, key;for (i 1; i length; i){key array;// 把i之前大于array的数据向后移动for (j i - 1; j 0 array[j] key; j--){array[j 1] array[j];}// 在合适位置安放当前元素array[j 1] key;}
}2.shell排序 原理将序列分成子序列然后分别对子序列进行排序最后将子序列组合起来。每次排序把序列的元素按照某个增量分成几个子序列对这几个子序列进行插入排序然后不断的缩小增量扩大每个子序列的元素数量直到增量为一的时候子序列就和原先的待排列序列一样了此时只需要做少量的比较和移动就可以完成对序列的排序了。 // shell排序
void ShellSort(int array[], int length)
{int temp;// 增量从数组长度的一半开始,每次减小一倍for (int increment length / 2; increment 0;increment / 2)for (int i increment; i length; i){temp array;// 对一组增量为increment的元素进行插入排序for (int j i; j increment; j - increment){// 把i之前大于array的数据向后移动if (temp array[j - increment]){array[j] array[j - increment];}else{break;}}// 在合适位置安放当前元素array[j] temp;}
}3.冒泡排序 原理每次遍历完序列都把最大小的元素放在最前面然后再对剩下的序列重复前面的一个过程每次遍历完之后待排序序列就少一个元素当待排序序列减小为只有一个元素的时候排序就结束了。因此复杂度在最坏的情况下是ON ^ 2 冒泡排序是稳定的不会改变相同元素的相对顺序。 void Swap( int * a, int * b){int temp;temp * a;* a * b;* b temp;
}// 冒泡排序void BubbleSort( int array[], int length){// 记录一次遍历中是否有元素的交换总是与相邻的元素比较并向前移bool exchange;for ( int i 0 ; ilength; i){exchange false ;for ( int ji1 ; j length;j){if (array[j] array){exchange true ;Swap( array[j], array);}}// 如果这次遍历没有元素的交换,那么排序结束if ( false exchange)break ;}
}4.快速排序 原理选定一个枢纽元素对待排序序列进行分割分割之后的序列一个部分小于枢纽元素一个部分大于枢纽元素再对这两个分割好的子序列进行上述的过程。 假设输入的数组中有k个小于轴值的结点于是这些结点被放到数组最左边的k个位置上而大于轴值得被放到数组最右边的n-k个位置上。 // 对一个给定范围的子序列选定一个枢纽元素,执行完函数之后返回分割元素所在的位置,
// 在分割元素之前的元素都小于枢纽元素,在它后面的元素都大于这个元素
int Partition(int array[], int low, int high)
{// 采用子序列的第一个元素为枢纽元素int pivot array[low];while (low high){// 从后往前在后半部分中寻找第一个小于枢纽元素的元素while (low high array[high] pivot){--high;}// 将这个比枢纽元素小的元素交换到前半部分Swap(array[low], array[high]);// 从前往后在前半部分中寻找第一个大于枢纽元素的元素while (low high array[low] pivot){low;}// 将这个比枢纽元素大的元素交换到后半部分Swap(array[low], array[high]);}// 返回枢纽元素所在的位置return low;
}// 快速排序
void QuickSort(int array[], int low, int high)
{if (low high){int n Partition(array, low, high);QuickSort(array, low, n);QuickSort(array, n 1, high);}
}5. 归并排序 原理把待排序序列分成相同大小的两个部分依次对这两部分进行归并排序完毕之后再按照顺序进行合并 两个(或两个以上)有序表合并成一个新的有序表,即把待排序的序列分成若干个子序列,每个子序列都是有序的,然后把有序子序列合并成整体有序序列,这个过程也称为2-路归并.归并排序的一种稳定排序,即相等元素的顺序不会改变.时间复杂度为Onlogn,空间复杂度为log(n) // 归并排序中的合并算法
void Merge(int array[], int start, int mid, int end)
{int temp1[10], temp2[10];int n1, n2;n1 mid - start 1;n2 end - mid;// 拷贝前半部分数组for (int i 0; i n1; i){temp1 array[start i];}// 拷贝后半部分数组for (int i 0; i n2; i){temp2 array[mid i 1];}// 把后面的元素设置的很大temp1[n1] temp2[n2] 1000;// 逐个扫描两部分数组然后放到相应的位置去for (int k start, i 0, j 0; k end; k){if (temp1 temp2[j]){array[k] temp1;i;}else{array[k] temp2[j];j;}}
}// 归并排序
void MergeSort(int array[], int start, int end)
{if (start end){int i;i (end start) / 2;// 对前半部分进行排序MergeSort(array, start, i);// 对后半部分进行排序MergeSort(array, i 1, end);// 合并前后两部分Merge(array, start, i, end);}
}6.选择排序 原理 每一趟从待排序的数据元素中选出最小或最大的一个元素 顺序放在已排好序的数列的最后直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。 第i次是选择数组中第i小的记录并将该记录放到数组的第i个位置。 package sort.select;
import java.util.Random;
/*** author liangge* */
public class Main {public static void main(String[] args) {Random ran new Random();int[] sort new int[10];for (int i 0; i 10; i) {sort[i] ran.nextInt(50);}System.out.print(排序前的数组为);for (int i : sort) {System.out.print(i );}selectSort(sort);System.out.println();System.out.print(排序后的数组为);for (int i : sort) {System.out.print(i );}}/*** 选择排序* param sort*/private static void selectSort(int[] sort){for(int i 0;isort.length-1;i){for(int j i1;jsort.length;j){if(sort[j]sort[i]){int temp sort[j];sort[j] sort[i];sort[i] temp;}}}}
}7.堆排序 堆的定义 n个关键字序列KlK2…Kn称为堆当且仅当该序列满足如下性质简称为堆性质 1 ki≤K2i且ki≤K2i1 或2Ki≥K2i且ki≥K2i11≤i≤ 满足Key[i]Key[2i1]keykey[2i2]称为大顶堆满足 Key[i]key[2i1]Key[i]key[2i2]称为小顶堆。由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的小顶堆的堆顶的关键字是所有关键字中最小的 若将此序列所存储的向量R[1……n]看做是一棵完全二叉树的存储结构则堆实质上是满足如下性质的完全二叉树树中任一非叶结点的关键字均不大于或不小于其左右孩子若存在结点的关键字。 堆的这个性质使得可以迅速定位在一个序列之中的最小大的元素。 堆排序算法的过程如下1得到当前序列的最小大的元素 2把这个元素和最后一个元素进行交换这样当前的最小大的元素就放在了序列的最后而原先的最后一个元素放到了序列的最前面 3的交换可能会破坏堆序列的性质注意此时的序列是除去已经放在最后面的元素因此需要对序列进行调整使之满足于上面堆的性质。重复上面的过程直到序列调整完毕为止。 // array是待调整的堆数组,i是待调整的数组元素的位置,length是数组的长度
void HeapAdjust(int array[], int i, int nLength)
{int nChild, nTemp;for (nTemp array; 2 * i 1 nLength; i nChild){// 子结点的位置是 父结点位置 * 2 1nChild 2 * i 1;// 得到子结点中较大的结点if (nChild ! nLength - 1 array[nChild 1] array[nChild])nChild;// 如果较大的子结点大于父结点那么把较大的子结点往上移动,替换它的父结点if (nTemp array[nChild]){array array[nChild];}else // 否则退出循环{break;}}// 最后把需要调整的元素值放到合适的位置array nTemp;
}// 堆排序算法
void HeapSort(int array[], int length)
{// 调整序列的前半部分元素,调整完之后第一个元素是序列的最大的元素for (int i length / 2 - 1; i 0; --i){HeapAdjust(array, i, length);}// 从最后一个元素开始对序列进行调整,不断的缩小调整的范围直到第一个元素for (int i length - 1; i 0; --i){// 把第一个元素和当前的最后一个元素交换,// 保证当前的最后一个位置的元素都是在现在的这个序列之中最大的Swap(array[0], array);// 不断缩小调整heap的范围,每一次调整完毕保证第一个元素是当前序列的最大值HeapAdjust(array, 0, i);}
}时间复杂度 平均情况 最好情况 最坏情况 归并排序 O(nlogn) O(nlogn) O(nlogn) 快速排序 O(nlogn) O(nlogn) O(n2) 希尔排序 O(n1.5) O(n) O(n1.5) 插入排序 O(n2) O(n) O(n2) 选择排序 O(n2) O(n2) O(n2) 堆排序时间复杂度O(nlogn) 选择排序时间复杂度On2 冒泡排序时间复杂度On2
