几种常用排序整理

标签：稳定性   相等   现在   bre   数据   相同   存在   元素   lan   

排序分为内排和外排：

三种基本的内排算法：

1.插入排序：

有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，而插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。

　　　　　　　　　4　　8　　2　　0　　9　　5　　7　　1　　5　　6　　3

　　　　　　　（4）（8　　2　　0　　9　　5　　7　　1　　5　　6　　3）　　//第一趟

　　　　　　　　  (4　   8)　   (2　  0　　9　　5　　7　　1　　5　　6　　3) 　　 //第二趟

　　　　　　　  (2　　4　　8)　 (0　　9　　5　　7　　1　　5　　6　　3)　　  //第三趟

　　　　　　　  (0　　2　　4　　8)　 (9　　5　　7　　1　　5　　6　　3)　　  //第四趟

　　　　　　　　　　　　　　　　　　　  .......

是稳定的排序算法。时间复杂度的基本运算如果按比较和移动相同的话，则，时间复杂度固定为O(n*(n-1)/2)  =>O(n*n)。

最优的情况和最差的情况相同：

最优的情况（完全顺序），则，比较次数最多，移动次数为0；

最差的情况（完全逆序），则，比较次数最少，移动次数最多。

实现代码如下：

 1 void insertSort(int *data,int count){
 2     int fi;
 3     int j;
 4     
 5     for(fi = 1;fi //无序数组 
 6         int i ;
 7         int tmp = data[fi];            //有序数的数组data[]; 
 8         for(i = 0;i ){
 9             if(data[i] > tmp){   //需要插入的data[i]和有序的tmp比较； 
10                 break;
11             }
12             for(j = fi;j > i;j--){    //移动 
13                 data[j] = data[j-1];
14             }
15             data[i] = tmp;
16         }
17     }
18 } 

2.选择排序：

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

举个例子来说明：

　　　　　　　4　　7　　2　　5　　9　　1　　5　　8　　6　　3

　　　　　　 （） （4　　7　　2　　5　　9　　1　　5　　8　　6　　3）　　//第一趟

　　　　　　（1）（7　　2　　5　　9　　4　　5　　8　　6　　3）　　　　//第二趟

　　　　　　（1　　2）（7　　5　　9　　4　　5　　8　　6　　3）　　　　//第三趟

　　　　　　（1　　2　　3）（5　　9　　4　　5　　8　　6　　7）　　　　//第四趟

　　　　　　　　　　　　　　........

稳定性分析：

 1 void chooseSort(int *data,int count){
 2     int index;
 3     int i ;
 4     int minIndex;
 5     int tmp;
 6     
 7     for(index = 0;index 1;index++){        //遍历整个数组 
 8         for(minIndex = i = index;i //拿出未排序第一个数与后面的数比较 
 9             if(data[minIndex] > data[i]){          //找到最小的 就是拿出来的那个数 
10                 minIndex = i;
11             }
12         }
13         if(minIndex != index){        //若拿出来的数不是最小的 
14             tmp = data[index];            //把拿出的这个数和后面比较出来最小的交换。 
15             data[index] = data[minIndex];
16             data[minIndex] = tmp;
17         }
18     }
19 }

举个例子来说明：

　　　　　　　　6　　9　　2　　0　　8　　1　　7　　2　　3　　5　　4

　　　　　　　　6　　2　　0　　8　　1　　7　　2　　3　　5　　4　　9

　　　　　　　　2　　6　　6　　1　　7　　2　　3　　5　　4　　8　　9

　　　　　　　　　　　　                      ..........

稳定性：

由于在直接选择排序中存在着不相邻元素之间的互换，因此，直接选择排序是一种不稳定的排序方法。

时间复杂度：

 1 void swapSort(int * data;int count){
 2     boolean swap = TRUE;
 3     int tmp;
 4     
 5     for(int i = 0;swap&&i 1;i++){
 6         for(swap = FALSE,j = 0;j 1-i;j++){
 7             if(data[j] > data[j+1]){
 8                 tmp = data[j];
 9                 data[j] = data[j+1];
10                 data[j+1] = tmp;
11                 swap = TRUE;
12             }
13         }
14     } 
15 } 

几种常用排序整理

标签：稳定性   相等   现在   bre   数据   相同   存在   元素   lan   

原文地址：https://www.cnblogs.com/youdiaodaxue16/p/9690484.html