to myself 的分类学习日志

做自己想做的事
posts - 232, comments - 6, trackbacks - 0, articles - 0
几种常用的排序算法? 八种? 十种?/Files/toMyself/最常用的排序算法总结.doc
参考:http://en.wikipedia.org/wiki/Sorting_algorithm 

排序,从小大,0坐标的在下面,即排序后小的在下面,大的在上面。

1,冒泡Bubble:从第0个开始,一直往上,与相邻的元素比较,如果下面的大,则交换。
Analysis:
Implementation:
void BubbleSort(int *pData, int iNum)



2,插入Insertion:与打扑克牌时整理牌很想象,假定第一张牌是有序的,从第二张牌开始,拿出这张牌来,往下比较,如果有比这张牌大的,则把它拨到上一个位置,直到找到比手上的这张更小的(或到顶了),
则把手上的这张牌插入到这张更小的牌的后面。
Analysis:
Implementation:
void InsertionSort(int *list, int length)
{
    
int i, j, temp;
    
for (i = 1; i < length; i++)
    
{
        temp 
= list[i];
        j 
= i - 1;
        
while ((j >= 0&& (list[j] > temp))
        
{
            list[j
+1= list[j];
            j
--;
        }

        list[j
+1= temp;
    }

}



3,选择Selection:从所有元素中找到最小的放在0号位置,从其它元素(除了0号元素)中再找到最小的,放到1号位置,......。
Analysis:
Implementation:
void SelectionSort(int data[], int count)
{
    
int i, j, min, temp;
    
for (i = 0; i < count - 1; i++
    
{
        
/* find the minimum */
        min 
= i;
        
for (j = i+1; j < count; j++)
        
{
            
if (data[j] < data[min])
            
{
                min 
= j;
            }

        }

        
/* swap data[i] and data[min] */
        temp 
= data[i];
        data[i] 
= data[min];
        data[min] 
= temp;
    }

}



4,快速Quick:先拿出中间的元素来(值保存到temp里),设置两个索引(index or pointer),一个从0号位置开始往最大位置寻找比temp大的元素;一个从最大号位置开始往最小位置寻找比temp小的元素,找到了或到顶了,则将两个索引所指向的元素
互换,如此一直寻找交换下去,直到两个索引交叉了位置,这个时候,从0号位置到第二个索引的所有元素就都比temp小,从第一个索引到最大位置的所有元素就都比temp大,这样就把所有元素分为了两块,然后采用前面的办法分别排序这两个部分。总的来
说,就是随机找一个元素(通常是中间的元素),然后把小的放在它的左边,大的放右边,对左右两边的数据继续采用同样的办法。只是为了节省空间,上面采用了左右交换的方法来达到目的。
Analysis:
Implementation:
void QuickSort(int *pData, int left, int right)
{
    
int i, j;
    
int middle, iTemp;
    i 
= left;
    j 
= right;

    middle 
= pData[(left + right) / 2]; //求中间值
    do
    
{
        
while ((pData[i] < middle) && (i < right)) //从左扫描大于中值的数
            i++;
        
        
while ((pData[j] > middle) && (j > left)) //从右扫描小于中值的数
            j--;
        
        
if (i <= j) //找到了一对值
        {
            
//交换
            iTemp = pData[i];
            pData[i] 
= pData[j];
            pData[j] 
= iTemp;
            i
++;
            j
--;
        }

    }
 while (i <= j); //如果两边扫描的下标交错,就停止(完成一次)

    
//当左边部分有值(left<j),递归左半边
    if(left < j) 
        QuickSort(pData, left, j); 
    
    
//当右边部分有值(right>i),递归右半边
    if(right > i) 
        QuickSort(pData, i, right); 
}


5,希尔Shell:是对Insertion Sort的一种改进,在Insertion Sort中,从第2个位置开始取出数据,每次都是与前一个(step/gap==1)进行比较。Shell Sort修改为,在开始时采用较大的步长step,
从第step位置开始取数据,每次都与它的前step个位置上的数据进行比较(如果有8个数据,初始step==4,那么pos(4)与pos(0)比较,pos(0)与pos(-4),pos(5)与pos(1),pos(1)与pos(-3),
...... pos(7)与pos(3),pos(3)与pos(-1)),然后逐渐地减小step,直到step==1。step==1时,排序过程与Insertion Sort一样,但因为有前面的排序,这次排序将减少比较和交换的次数。
Shell Sort的时间复杂度与步长step的选择有很大的关系。Shell排序比冒泡排序快5倍,比插入排序大致快2倍。Shell排序比起QuickSort,MergeSort,HeapSort慢很多。但是它相对比较简单,它适合
于数据量在5000以下并且速度并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的。
Analysis:
Implementation:
template<typename RandomIter, typename Compare>
void ShellSort(RandomIter begin, RandomIter end, Compare cmp)
{
    typedef typename std::iterator_traits
<RandomIter>::value_type value_type;
    typedef typename std::iterator_traits
<RandomIter>::difference_type diff_t;

    diff_t size 
= std::distance(begin, end);
    diff_t step 
= size / 2;
    
while (step >= 1)
    
{

      
for (diff_t i = step; i < size; ++i)
      
{
          value_type key 
= *(begin+i);
          diff_t ins 
= i; // current position
          
          
while (ins >= step && cmp(key, *(begin+ins-step)))
          
{
              
*(begin+ins) = *(begin+ins-step);
              ins 
-= step;
          }

          
          
*(begin+ins) = key;
      }

      
      
if(step == 2)
          step 
= 1;
      
else
          step 
= static_cast<diff_t>(step / 2.2);
    }

}



template
<typename RandomIter>
void ShellSort(RandomIter begin, RandomIter end) 
{
    typedef typename std::iterator_traits
<RandomIter>::value_type value_type;
    ShellSort(begin, end, std::less
<value_type>());
}


6,归并Merge:先将所有数据分割成单个的元素,这个时候单个元素都是有序的,然后前后相邻的两个两两有序地合并,合并后的这两个数据再与后面的两个合并后的数据再次合并,充分前面的过程直到所有的数据都合并到一块。
通常在合并的时候需要分配新的内存。
Analysis:
Implementation:
void Merge(int array[], int low, int mid, int high)
{
    
int k;
    
int *temp = (int *) malloc((high-low+1* sizeof(int)); //申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
    int begin1 = low;
    
int end1 = mid;
    
int begin2 = mid + 1;
    
int end2 = high;

    
for (k = 0; begin1 <= end1 && begin2 <= end2; ++k)  //比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
    {
        
if(array[begin1]<=array[begin2])
        
{
            temp[k] 
= array[begin1++];
        }

        
else
        
{
            temp[k] 
= array[begin2++];
        }

    }

    
if(begin1 <= end1) //若第一个序列有剩余,直接拷贝出来粘到合并序列尾
    {
        memcpy(temp
+k, array+begin1, (end1-begin1+1)*sizeof(int));
    }

    
if(begin2 <= end2) //若第二个序列有剩余,直接拷贝出来粘到合并序列尾
    {
        memcpy(temp
+k, array+begin2, (end2-begin2+1)*sizeof(int));
    }

    memcpy(array
+low, temp, (high-low+1)*sizeof(int));//将排序好的序列拷贝回数组中
    free(temp);
}

void MergeSort(int array[], unsigned int first, unsigned int last)
{
    
int mid  = 0;
    
if (first < last)
    
{
        mid 
= (first+last)/2;
        MergeSort(array, first, mid);
        MergeSort(array, mid
+1,last);
        Merge(array,first,mid,last);
    }

}


7,堆Heap:一棵堆积树(堆)满足条件:子结点的键值或索引总是小于(或者大于)它的父节点。

堆排序适合于数据量非常大的场合(百万数据)。

堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录,因为快速排序,归并排序都使用递归来设计算法,在数据量非常大的时候,可能会发生堆栈溢出错误。

堆排序会将所有的数据建成一个堆,最大的数据在堆顶,然后将堆顶数据和序列的最后一个数据交换。接下来再次重建堆,交换数据,依次下去,就可以排序所有的数据。

特点
  堆排序(HeapSort)是一树形选择排序。堆排序的特点是:在排序过程中,将R[l..n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系(参见二叉树的顺序存储结构),在当前无序区中选择关键字最大(或最小)的记录
堆排序与直接选择排序的区别
  直接选择排序中,为了从R[1..n]中选出关键字最小的记录,必须进行n-1次比较,然后在R[2..n]中选出关键字最小的记录,又需要做n-2次比较。事实上,后面的n-2次比较中,有许多比较可能在前面的n-1次比较中已经做过,但由于前一趟排序时未保留这些比较结果,所以后一趟排序时又重复执行了这些比较操作。
  堆排序可通过树形结构保存部分比较结果,可减少比较次数。
算法分析
  堆[排序的时间,主要由建立初始]堆和反复重建堆这两部分的时间开销构成,它们均是通过调用Heapify实现的。
  堆排序的最坏时间复杂度为O(nlogn)。堆序的平均性能较接近于最坏性能。
  由于建初始堆所需的比较次数较多,所以堆排序不适宜于记录数较少的文件。
  堆排序是就地排序,辅助空间为O(1),
  它是不稳定的排序方法。
  
  实际上,堆的构建和更新都可以使用非递归的方式实现,对于堆的构建,需要首先找到最后一个有孩子的节点array[k],然后从array[k]一直更新到array[0]即可,其中的k=n/2。k的求法如下:假设k存在

,2*k+1=n或者2*k+2=n,对于第一种情况,k==n/2,对于第二种情况,k==n/2-1。对于堆的更新,就更简单了,只要从array[0]开始,选择一条通路,一直向下更新,直到没有孩子了为止。
  值得注意的是,对于下标从0开始的数组,k号节点的孩子节点分别是2*k+1和2*k+2。而对于下标从1开始得数组,k号节点的孩子节点分别是2*k和2*k+1。
  堆排序属于选择排序,实际上就是利用最大堆这个数据结构,每次选择一个剩余元素中最大的元素,交换到合适的位置上去。

/*單一子結點最大堆積樹調整*/
void Max_Heapify(int A[], int i, int heap_size)
{
    
int l = 2 * i; // 左子結點
    int r = 2 * i + 1// 右子結點
    int largest;
    
int temp;
    
if(l < heap_size && A[l] > A[i])
    
{
        largest 
= l;
    }

    
else
    
{
        largest 
= i;
    }

    
if(r < heap_size && A[r] > A[largest])
    
{
        largest 
= r;
    }

    
if(largest != i)
    
{
        temp 
= A[i];
        A[i] 
= A[largest];
        A[largest] 
= temp;
        Max_Heapify(A, largest, heap_size);
    }

}

 
/*建立最大堆積樹*/
void Build_Max_Heap(int A[], int heap_size)
{
    
for(int i = heap_size; i >= 0; i--)
    
{
        Max_Heapify(A, i, heap_size);
    }

}

 
/*堆積排序程序碼*/
void HeapSort(int A[], int heap_size)
{
    
int temp;
    Build_Max_Heap(A, heap_size);
    
for(int i = heap_size - 1; i >= 1; i--)
    
{
        temp 
= A[0];
        A[
0= A[i];
        A[i] 
= temp;
        heap_size 
= heap_size - 1;
        Max_Heapify(A, 
0, heap_size);
    }

}



8,基数Radix:采用的是一种数据位的比较,比如比较整数的个位、十位等,比较字符串的第一个字符、第二个字符等。
参考:http://en.wikipedia.org/wiki/Radix_sort


9,计数Counting:


10,桶/箱Bucket:


测试:
1,测试数据只有1个、2个、3个、4个、5个。
2,测试数据很大,有奇数个、有偶数个。
3,测试数据中有多个是相等的值。


注:
附件中上传了一个我从往上找来的,别人对常用排序算法的总结,看看别人的描述,再看看自己的,很多地方都说得不大清楚,什么时候能够达到人家那样的水平,排序算法差不多也能过了吧!


扩展:
1,貌似所有的排序都以可随机访问的数组(array or vector or string)为例,其它存储方式(链表list)的数据的排序怎么办呢?
2,排序举例的时候大都以整形数的排序为例,如果是其它数据结构的排序怎么办了? 有没有更通用的排序算法实现?比较、交换两种操作单独写成函数指针或函数对象,可行吗?
3,几种算法更加C++化的实现?




只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理