【求正解】100分求冒泡排序、快速排序、选择排序原理

Question

当初学习的时候给弄迷糊了，现在也没搞明白，今天笔试遇到了，求解一下，要正解给分，比如有一个排序是弄俩数平均一下再怎么地，我给忘记了，求正解啊。

Answer 1

这种原理性问题，去Google去搜索下原理不是更快？

Answer 2

1，选择排序：先找到数列中最小的数，放到数列的最前面；接着在剩下的数里面找最小数，放到刚才那个最小数的后面，依此类推，就能实现排序。
实现过程：5 3  8 7 2 1
第一步：先找到最小的 1   1和5 交换位置                       1 3 8 7 2 5
第二步： 保持1 的位置不变 找第二个最小的数2 与3 交换位置      1 2 8 7 3 5
第三步：保持1和2 的位置不变，找下一个最小的数3与8交换位置      1 2 3 7 8 5
.....
到最后 得到正确的排列顺序：                                   1 2 3 5 7 8     方法代码：
for（int i =0;i<list.length-1;i++）
{
select the smallest element in list[i...list.length-1];
swap the smallest with list[i],if necessary;
}
实现的代码：
public class SelectionSort
{
public static void  selectionSort（double[] list）
{
for(int i = 0;i<list.length-1;i++)//迭代遍历整个数组
{
double currentMin = list[i];//找到最小的那个数
int currentMinIndex = i;//最小的索引为i
for(int j = i+1;j<list.length;j++)//迭代遍历剩下的整个数组
{
if(currentMin > list[j])//如果找到的最小的那个比以前的那个最小的小，则重新给最小的赋值
{
currentMin = list[j];
currentMinIndex = j;
}
}
if(currentMinIndex != i)
{
list[currentMinIndex] = list[i];
list[i] = currentMin;
}
}
}
}
2：插入排序：在已经排好的子序列中反复插入一个新的元素进行排序，知道整个数列排好序；
实现的代码：
实现过程：5 3  8 7 2 1
第一步： 先初始状态，确定一个元素5；
第二步： 3与5进行比较 3比5小排在5的前面；
第三步： 3 与5 确定插入8,8比5大，排在5后面；
...
到最后插入1 比任何一个值都小，排在第一个位置，排序完成；public class  InsertionSort
{
public static void insertionSort(double [] list)
{
for(int i = 0;i<list.length;i++)//迭代遍历整个数组
{
double currentElemnt = list[i];//确定一个元素作为比较的基准
int k;
for(int k = i - 1;k>=0&&list[k]>currentElemnt;k--)//继续遍历剩下的数组，一个元素一个元素的插入，如果比                                                      以前确定的那个元素大，放在后面，否则放在前面
{
list[k+1] = list[k];}
list[k+1] = currentElemnt;
}
}
}
3：冒泡法排序：
如果一对元素降序排列，则互换他们的值，否则保持一致；较小的数字想气泡一样逐渐浮到顶部，而较大的沉底；
实现过程： 2 9 5 4 8 1
第一次：2 5 4 8 1 9
第二步：2 5 4 1 8 9
第三步：2 4 1 5 8 9
第四步：2 1 4 5 8 9
第五步：1 2 4 5 8 9     六个数字最后比较五次：如果N个数，最多比较N-1；
代码：
for（int k =1;k<list.length;k++）
{
for(int i = 0;i<list.length-k;i++)
{
if(list[i] > list[i+1])
{
swap list[i] with list[i+1];
}
}
}
4.归并排序：
将数组分为两半，对每部分递归的应用归并排序，两部分排好后，对他们进行归并；
实现过程：
实现过程： 2 9 5 4 8 1 7  6
第一次分：（2 9 5 4 ）           （8 1 7 6）
第二次分： (2 9)  (5 4)          (8 1)  (7 6)
第三次分：2  9   5   4          8  1   7   6
进行归并：
（2 9 ）（4 5 ）           （1   8 ）（6   7）
归并（ 2 4 5 9） （1  6 7 8）
最后一次归并（1  2 4 5  6 7 8 9）
实现代码;
public static void mergeSort(int [] list)
{
if(list.length>1)
{
mergeSort(list[0...list.length/2]);
merge list[0...list.length/2]with
list[list.length/2+1...list.length];}
}
 5：希尔排序：是插入排序的一种变体,再插入排序的过程中，数组元素移动到相邻的位置；
实现过程： 2 9 5 4 8 1 7  6
第一步： 2 9 5 4 8 1 7 6
         2-------8-------
           9-------1------
             5-------7-----
               4--------6------
对一直线上的两个元素排序：
          2--------8-------
            1---------9------
              5----------7-----
                4-----------6--------
排序后的结果：2 1 5 4 8 9 7 6
第二步：      2---5---8---7
                1--4---9----6对一条直线上的进行排序 2---5--7---8
                        1---4--6---9
 排序后：            2 1  5 4 7 6 8 9
在对这个数组进行简单的插入排序就可以了：
实现代码：
public static void incrementalInsertionSort(T[] a ,int first,int last,int space)
{
int unsorted,index;
for(unsorted = first+space;unsort<=last;unsorted = unsorted+pace)
{
T firstUnsorted = a[unsorted];
for(index = unsorted-space;(index>=first)&&(firstUnsorted.compareto(a[index])<0);index = index-space)
{
a[index+space] = a[index];
}
a[index+space]= firstUnsorted;
}
}                     
快速排序：这个方法选择主元素，将数组分为两部分，使得一部分小于主元素，一部分大于主元素，对于主元素两边的部分，应该运用选择递归快速排序的方法，  为了排序的效率一般选择第一个元素为主元素。
 形式： list1    pivot   list2
实现过程： 5 2 9 3 8 4 0 1 6 7
 5 2 9 3 8 4 0 1 6 7       原始数组                    确定5为主元素  
 4 2 1 3 0 5 8 9 6 7        划分原始数组
 0 2 1 3 4                  划分子数组     4 2 1 3 0    确定3为主元素
 0 2 1 3                     划分子数组    0 2 1 3      确定2为主元素
 1 2 3                        划分数组     2 1 3
在这个快速排序的过程中 确定了一个主元素后，就要进行排序。从左到右依次找比主元素大的元素，再从右到左依次找比主元素小的元素，等两边都找到元素后，交换这两个数字。一次这样划分数组。
代码：
public static void quickSort(int [] list)
{
if(list.length>1)
{
seclet a pivot;
partition list into list1 and list2 such that
all elements in list1 <= pivot and all elements in list2 >
quickSort(list1)
quickSort(list2);
}
}
桶排序：0——（N-1）个键值，如果元素键值为1 ，那么就将该元素放入桶i中，每个桶中都存在与键值相同元素的值。
实现过程：331  454  230  34  343  45  59 453  345  231  9  
第一步：将最后一位按0——9的顺序依次放入bucket[i]中（o<i<9）
bucket[0]  bucket[1]  bucket[2]  bucket[3]   bucket[4]   ......               bucket[9]
230      331  231                343 453        454      45 345                59  9
bucket[]： 230  331 231 343 453 454  45 345 59 9
第二步：将倒数第二数放入桶中
bucket[0]  bucket[1]  bucket[2]             ....                                    bucket[9]
  9                             230 331 231 34     343 45 345     453 454 59   
  将桶删除后： 9  230 331 231  34 343 45 345 453 454  59
第三步： 将倒数第三个数放入桶中：
bucket[0]  bucket[1]  bucket[2]  bucket[3]   bucket[4]   ......               bucket[9]       
9 34 45 59            230 231    331 343 345   453
 将桶删除后：9  34  45  59   230  231  331  343  345 453  
现在进行比较这些数字就有序了；
代码：public bucketSort(E [] list)
{
E[] buckets =(E[]) new java.util.ArrayList[N];
for(int i = 0;i<list.length;i++)
{
int key = list[i].getkey();
if(buckets[i] != null)
{
for(int j = 0;j<buckets[i].size();j++)
list[k++] = buckets[i].get(j);}
}
}

Answer 3

LZ所说那是冒泡排序。取平均，然后像冒泡一样逐层递归。越来越大。好像还有个插入排序吧。我用的是C语言。

Answer 4

lz可以看看我做的排序动画，http://blog.csdn.net/wangdong20/article/details/7851969