算法之七种排序，七种排序
算法之七种排序，七种排序
插入排序
public static void insertSort(int[] t){
for(int i=1; i<t.length; i++){
//将第i个数提取出来
int temp = t[i];
int j;
for(j=i-1; j>=0 && temp<t[j]; j--){
//如果提取出来的那个数小于t[j]，数据里面的数就往后移。
t[j+1] = t[j];
}
//提取出来的数大于或等于t[j]，就插入到t[j]的后一个位置上（即t[j+1]）
t[j+1] = temp;
}
}
时间复杂度：最好情况为O(n)； 最坏情况为：O(n^2)，是稳定的。
希尔排序
public static void shellSort(int[] t){
//不断缩小比较数据之间的位置，直到变成插入排序
for(int delta=t.length/2; delta>0; delta/=2){
//原理和插入排序一样，
//只是将1换成delta而已
for(int i=delta; i<t.length; i++){
int temp=t[i];
int j;
for(j=i-delta; j>=0 && temp<t[j]; j-=delta){
t[j+delta] = t[j];
}
t[j+delta] = temp;
}
}
}基本思想是分组的直接插入排序。时间复杂度为：O(n(㏒2n)²)，那个2是指下标的2（下同），是不稳定的。
冒泡排序
public static void bubbleSort(int[] t){
//是否交换的标记
boolean exchange = true;
//每循环一次，就会得到一个最大值
for(int i=1; i<t.length && exchange; i++){
exchange = false;
for(int j=0; j<t.length-i; j++){
if(t[j]>t[j+1]){
int temp = t[j+1];
t[j+1] = t[j];
t[j] = temp;
exchange = true;
}
}
}
}基本思想是：比较相邻两个元素的关键字值，如果反序，则交换。如果按升序排序，每一趟将被扫描的数据序列中的最大元素交换到最后位置，就像气泡从水里冒出一样。 时间复杂度：最好情况：O(n)； 最坏情况：O(n²)，是稳定的
快速排序
public static void quickSort(int[] t){
quickSort(t,0,t.length-1);
}
private static void quickSort(int[] t, int begin, int end) {
//判断序列是否有效
if(begin<end){
int i=begin, j=end;
//提取基准值
int vot = t[i];
while(i!=j){
//从后面寻找较小值
while(i<j && vot <= t[j]){
j--;
}
if(i<j){
//较小值往前移动
t[i++] = t[j];
}
//从前面寻找较大值
while(i<j && t[i]<=vot){
i++;
}
if(i<j){
//较大值往后移动
t[j--] = t[i];
}
}
//确定基准值的位置
t[i]=vot;
//前端子序列在排序，递归调用
quickSort(t,begin,j-1);
//后端子序列在排序，递归调用
quickSort(t,i+1,end);
}
}基本思想是：在数据序列中选择一个值作为比较的基准值，每趟从数据序列的两端开始交替进行，将小于基准值的元素交换到序列前端，将大于基准值的元素交换到序列后端，介于两者之间的位置则成为基准值的最终位置。同时，序列被划分成两个子序列，再用同样的方法分别对两个子序列进行排序，直到子序列的长度为1，则完成排序。 时间复杂度：最好的情况：O(n*㏒2n)； 最坏的情况：O(n²)；是不稳定的。
直接选择排序
public static void selectSort(int[] t){
for(int i=0; i<t.length-1; i++){
//标记最小值的位标
int min=i;
//遍历寻找最小值
for(int j=i+1; j<t.length; j++){
if(t[j]<t[min]){
min=j;
}
}
//将最小值交换到前面
if(min!=i){
int temp = t[i];
t[i] = t[min];
t[min] = temp;
}
}
}基本思想：第一趟从n个元素的数据序列中选出关键字最小（或最大）的元素并放到最前（或最后）位置，下一趟再从n-1个元素中选出最小（大）的元素并放到次前（后）位置。以此类推，经过n-1趟完成排序。 时间复杂度：最好情况：O(n²)； 最坏情况：O(n²)； 是不稳定的。
堆排序
//将以begin为根的子树调整成最小堆
private static void sift(int[] t,int begin, int end){
//j为i结点的左孩子
int i=begin, j=2*i+1;
//子树根节点的值
int temp=t[i];
while(j<=end){
//比较左右孩子，将j定位到最小那个
if(j<end && t[j]>t[j+1]){
j++;
}
if(temp>t[j]){
//若子树根节点的值较大，
//较小的孩子结点上移
t[i]=t[j];
//使i，j向下一层
i=j;
j=2*i+1;
}else{
break;
}
}
//当前子树的原根值调整后的位置
t[i]=temp;
}
public static void heapSort(int[] t){
int n=t.length;
//创建最小堆
for(int j=n/2-1; j>=0; j--){
sift(t,j,n-1);
}
//每趟将最小值交换到后面，再调整成堆
for(int j=n-1; j>0; j--){
int temp = t[0];
t[0] = t[j];
t[j] = temp;
sift(t,0,j-1);
}
}基本思想：首先和直接选择排序对比一下，在直接选择排序中，每趟从数据序列中选出一个最小值交换到前面，其余n-1个元素原地不动，下一趟需要再次比较这些元素，因此直接选择排序算法的重复比较很多。如果每趟能够利用前一趟的比较结果，则会减少一些重复比较，从而提高算法效率。堆排序就是利用完全二叉树的特性，每趟只需遍历树中的一条路径就行了，而不是全部元素。 时间复杂度：最好最坏情况都是：O(n*㏒2n)； 是不稳定的。
归并排序
//对子序列元素的操作,
//m和r分别是相邻的两个已排序子序列的起始下标，
//n为子序列的长度
private static void merge(int[] X, int[] Y, int m, int r, int n){
int i=m, j=r, k=m;
//将X中两个相邻子序列归并到Y中
while(i<r && j<r+n && j<X.length){
if(X[i] < X[j]){
//将较小值复制到Y中
Y[k++] = X[i++];
}else{
Y[k++] = X[j++];
}
}
//将前一个子序列剩余元素复制到Y中
while(i<r){
Y[k++] = X[i++];
}
//将后一个子序列剩余元素复制到Y中
while(j<r+n && j<X.length){
Y[k++] = X[j++];
}
}
//对子序列的操作
private static void mergepass(int[] X, int[] Y, int n){
int i = 0;
while(i < X.length-n*2+1){
merge(X, Y, i, i+n, n);
i += 2*n;
}
//对于剩余不够2n的子序列的操作
if(i+n < X.length){
//尽管后一个子序列长度不够n，
//但还是可以再来一次merge
merge(X, Y, i, i+n, n);
}else{
for(int j=i; j<X.length; j++){
Y[j]=X[j];
}
}
}
//对数组的操作
public static void mergeSort(int[] X){
int[] Y = new int[X.length];
int n = 1;
//一次while循环完成两趟并归，
//数据序列从X到Y，再从Y到X，
//使排序后的数据序列仍在数组X中
while(n<X.length){
mergepass(X,Y,n);
n*=2;
mergepass(Y,X,n);
n*=2;
}
}基本思想：n个元素的数据序列可看成是由n个长度为1的排序子序列组成，反复讲相邻的两个子序列归并成一个排序的子序列，直到合并成一个序列，则排序完成。 时间复杂度：最好最坏的情况都是：O(n*㏒2n)； 是稳定的。
测试方法
public static void main(String[] args) {
//创建一个数组
int[] y = new int[10];
//向数组赋值
for(int i=0; i<y.length; i++){
int a = new Random().nextInt(100);
y[i] = a;
}
//执行排序方法
selectSort(y);
//打印排序后的数组
for(int i=0; i<y.length; i++){
System.out.println(y[i]);
}
}如果读者有什么更好的建议或疑问，欢迎在下面评论，一起交流进步。
（1）“冒泡法”
冒泡法大家都较熟悉。其原理为从a[0]开始，依次将其和后面的元素比较,若a[0]>a[i]，则交换它们，一直比较到a[n]。同理对a[1],a[2],...a[n-1]处理，即完成排序。下面列出其代码：
void bubble(int *a,int n) /*定义两个参数：数组首地址与数组大小*/
{
int i,j,temp;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++) /*注意循环的上下限*/
if(a[i]>a[j]) {
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
冒泡法原理简单，但其缺点是交换次数多，效率低。
下面介绍一种源自冒泡法但更有效率的方法“选择法”。
（2）“选择法”
选择法循环过程与冒泡法一致，它还定义了记号k=i,然后依次把a[k]同后面元素比较，若a[k]>a[j],则使k=j.最后看看k=i是否还成立，不成立则交换a[k],a[i],这样就比冒泡法省下许多无用的交换，提高了效率。
void choise(int *a,int n)
{
int i,j,k,temp;
for(i=0;i<n-1;i++) {
k=i; /*给记号赋值*/
for(j=i+1;j<n;j++)
if(a[k]>a[j]) k=j; /*是k总是指向最小元素*/
if(i!=k) { /*当k!=i是才交换，否则a[i]即为最小*/
temp=a[i];
a[i]=a[k];
a[k]=temp;
}
}
}
选择法比冒泡法效率更高，但说到高效率，非“快速法”莫属，现在就让我们来了解它。
（3）“快速法”
快速法定义了三个参数，（数组首地址*a,要排序数组起始元素下标i,要排序数组结束元素下标j). 它首先选一个数组元素（一般为a[(i+j)/2],即中间元素）作为参照，把比它小的元素放到它的左边，比它大的放在右边。然后运用递归，在将它左，右两个子数组排序，最后完成整个数组的排序。下面分析其代码：
void quick(int *a,int i,int j)
{
int m,n,temp;
int k;
m=i;
n=j;
k=a[(i+j)/2]; /*选取的参照*/
do {
while(a[m]<k&&m<j) m++; /* 从左到右找比k大的元素*/
while(a[n]>k&&n>i) n--; /* 从右到左找比k小的元素*/
if(m<=n) { /*若找到且满足条件，则交换*/
temp=a[m];
a[m]=a[n];
a[n]=temp;
m++;
n--;
}
}while(m<=n);
if(m<j) quick(a,m,j); /*运用递归*/
if(n>i) quick(a,i,n);
}
（4）“插入法”
插入法是一种比较直观的排序方法。它首先把数组头两个元素排好序，再依次把后面的元素插入适当的位置。把数组元素插完也就完成了排序。
void ins......余下全文>>
七种排序算法：冒泡、选择、插入、快速、Bucket、Shell、Heap
其中冒泡是最简单、也是效率最低的一种排序方法，老师要求我们掌握的是选择排序法。
快速排序法可以说是最好的排序算法：首先选一个分界值，把大于分界值和小于分界值的数据分成两部分；对于分开的部分，不断重复这个过程，直到结束。
评论暂时关闭