简单排序总结

今天重新学习了一下简单排序：冒泡排序、选择排序、插入排序

1.冒泡排序

核心代码：

//a代表数组a,nElems代表数组长度
public void bubbleSort(){
     int out,in;
     for(out=nElems-1;out>1;out--){
           for(in=0;in<out;in++){//先将最大的数据放在最后
                if(a[in]>a[int+1])//比较
                    swap(in,in+1);//交换数据
           }
     }
}

 

思路：将最大的数据放在最后！从后面开始排序

效率：假设数据中有N个数据项，则共做了N*(N-1)/2次比较，交换次数平均大约为N²/4次， 此算法的运行时间为O(N²)

不变性：out右边的所有数据项均为有序

特点：运行比较慢，是排序算法中最简单的

2.选择排序

核心代码：

//a代表数组a,nElems代表数组长度
public void selectionSort(){
     int out,in,min;
     for(out=0;out<nElems-1;out++){
           min = out;//从开始把初值附给min
           //从第out的下一个数开始和min比较,直到找到最小的值
       for(in=out+1;in<nElems;in++){
              if(a[in]<a[min])//如果比a[min]小，则把最小值的下标附给min
                 min = in; 
           }
           swap(out,min);//交换数据
     }
}

  

思路：将最小的数据放在最前面,从前面开始排序

效率：假设数据中有N个数据项，则共做了N*(N-1)/2次比较，但交换比冒泡排序少的多O(N)！算法的运行时间为O(N²)

不变性：下标小于或等于out的数据项总是有序的

特点：运行比冒泡快一点

3.插入排序

 

核心代码：

//a代表数组a,nElems代表数组长度
public void insertionSort(){
     int out,in;
     for(out=1;out<nElems;out++){
           long temp = a[out];//声明一个被标记的变量
       in = out;//从out开始
       while(in>0&&a[in-1]>=temp){
                a[in] = a[in-1]//a[in]如果比a[in-1]小，则进行附值，直接替换
           --in; //in自减1，意思是向左移一位
       }
           a[in] = temp;//in已经找到位置，左边的都是比a[in]小的
     }
}

   

思路：选择一个标记，在这个标记的左边已经是局部有序的了，然而左边数据的最终位置还没有确定！

效率：假设数据中有N个数据项，则共做了N*(N-1)/4次比较，但交换比冒泡排序少的多O(N)！算法的运行时间为O(N²)

对于有序或者基本有序的数据来说，插入排序要好的多，只需要O(N)的时间。

不变性：在每次结束时，在将temp位置的项插入后，比outer变量下标小的数据项总是局部有序的

特点：相对于随机数据，运行比冒泡快一倍，比选择排序要快一点