数据结构：四种排序的比较

对大数据进行排序时，冒泡排序、选择排序、奇偶排序、插入排序的效率不相同

各种排序的代码：

冒泡排序：

View Code

1 public void bubbleSort()
2       {
3       int out, in;
4 
5       for(out=nElems-1; out>1; out--)   // outer loop (backward)
6          for(in=0; in<out; in++)        // inner loop (forward)
7             if( a[in] > a[in+1] )       // out of order?
8                swap(in, in+1);          // swap them
9       }  // end bubbleSort()

选择排序：

View Code

 1 public void selectionSort()
 2       {
 3       int out, in, min;
 4 
 5       for(out=0; out<nElems-1; out++)   // outer loop
 6          {
 7          min = out;                     // minimum
 8          for(in=out+1; in<nElems; in++) // inner loop
 9             if(a[in] < a[min] )         // if min greater,
10                 min = in;               // we have a new min
11          swap(out, min);                // swap them
12          }  // end for(out)
13       }  // end selectionSort()

奇偶排序：

View Code

 1 public void oddEvenSort()//奇偶排序
 2   {
 3       boolean flag = false ;//用作标志
 4       while(!flag)
 5       {
 6           flag = true ;
 7           for(int i=1 ; i<a.length-1 ; i+=2)//奇数
 8           if(a[i]>a[i+1])
 9           {
10               swap(i,i+1) ;
11               oddScanNum++ ;
12               flag = false ;
13           }
14           
15           for(int i=0 ; i<a.length-1 ; i+=2)//偶数
16           if(a[i]>a[i+1])
17           {
18               swap(i,i+1) ;
19               evenScanNum++ ;
20               flag = false ;
21           }
22       }
23    }

插入排序：

View Code

 1 public void insertionSort()
 2       {
 3       int in, out;
 4 
 5       for(out=1; out<nElems; out++)     // out is dividing line
 6          {
 7          long temp = a[out];            // remove marked item
 8          in = out;                      // start shifts at out
 9          while(in>0 && a[in-1] >= temp) // until one is smaller,
10             {
11             a[in] = a[in-1];            // shift item to right
12             --in;                       // go left one position
13             }
14          a[in] = temp;                  // insert marked item
15          }  // end for
16       }  // end insertionSort()

对数据大小为10^4 ~ 10^5 进行排序，各种排序的所需的时间如下所示：

可以得出结论：对数据量不大时，四种排序所需的时间都差不多；对大数据时，四种排序所需的时间的比较为：冒泡排序<选择排序≈奇偶排序<插入排序