重新温习数据结构二:简单排序

这里并没有给出完整的例子,只是一些代码块.我说的是最核心的一些部分.
1、冒泡排序，这应该是性能最差的一种排序，不提倡用.

public void bubbleSort()
  {
  int out, in;
  for(out=nElems-1; out>1; out--)   // 外层的循环,nElems是数组的大小
     for(in=0; in<out; in++)        // 里面层的循环
        if( a[in] > a[in+1] )
           swap(in, in+1);          // 交换两个数
  }

交换的方法：

private void swap(int one, int two)
{
long temp = a[one];
a[one] = a[two];
a[two] = temp;
}

小结：冒泡排序的交换和比较操作的次数都和^N2成正比，排序需要O(N²)的时间级别.

2、选择排序的算法:

 

public void selectionSort()
    {
    int out, in, min;

    for(out=0; out<nElems-1; out++)   // 外层的循环,nElems是数组的大小
       {
       min = out;                     //最小值设为min
       for(in=out+1; in<nElems; in++) // 里面层的循环
          if(a[in] < a[min] )         // 如果有更小的值
              min = in;
       swap(out, min);                // 交换
       }
    }

小结：选择排序与冒泡排序执行了相同次数的比较N*(N-1)/2。当N值比较大时，比较的次数是主要，这时候采用选择排序性能也不好；当N值比较小的时候，选择排序的性能还是比较好的.

3、插入排序：性能比冒泡排序，选择排序好，在局部有序的情况下，插入排序的性能很好.

 

public void insertionSort()
      {
      int in, out;

      for(out=1; out<nElems; out++)
         {
         long temp = a[out];            // 标记一下
         in = out;
         while(in>0 && a[in-1] >= temp) // 直到有一个值比temp小的
            {
            a[in] = a[in-1];            // 移动出一个空位
            --in;
            }
         a[in] = temp;                  // 插入这一个值temp
         }
      }

小结：如果数组是基本有序或是有序了，这时候用插入排序只需要O(N)的时间。但如果对于逆序的数据，性能并不比冒泡排序快，这一点需要注意.

下一次会介绍多几种排序的，有空且心情好的时候再过来写写。