十大排序算法

class Sort
{
public :
    //每个算法都已升序为例

    //冒泡排序
    //算法思想：比较相邻的两个元素，如果前一个数比后一个数大，两者交换，一轮过后最大的数位于数组末尾，经过n-1轮
    //算法分析：O(n2)复杂度
    void bubbleSort(int *array,int begin,int end)
    {
       if(begin >= end)
         return ;
       for(int i = 0;i < end-begin;++i)//一共num-1轮
       {
           for(int j = 0;j < end-begin-i;++j)//每次从头开始
           {
               if(array[j] > array[j+1])
               {
                   int tmp = array[j+1];
                   array[j+1] = array[j];
                   array[j] = tmp;
               }
           }
       }
    }


    //选择排序
    //算法思想:
    //算法分析：O(n2)复杂度
    void selectSort(int *array,int begin,int end)
    {
       int min_value;

       for(int i = 0 ;i< end-begin;++i)
       {
           int min_value = array[i];
           int min_index = i;
           //寻找最小数
           for(int j = i+1;j<=end;++j)
           {
               if(min_value > array[j])
               {
                   min_value = array[j];
                   min_index = j;
               }

           }

           //交换

           array[min_index] = array[i];
           array[i] = min_value;

       }

    }

    //插入排序
    //算法思想:
    //算法分析：
    void insertSort(int *array,int begin,int end)
    {
       int tmp,i,j;


       for(int i = 1;i < end - begin+1;++i)
       {
           tmp = array[i];
           j = i-1;
           while(j >= begin && tmp < array[j])
           {
             array[j+1] = array[j];
             j--;
           }

           array [j+1] = tmp;
       }

    }

    //希尔排序
    //算法思想
    //算法分析
    void shellSort(int *array,int begin,int end)
    {
      int gap = (end - begin + 1);

      while(gap>0)
      {
          gap /=2;
          for(int i = 0;i <= end -gap; ++i) //注意是end-gap
          {
              if(array[i] > array[i+gap])
              {
                  int tmp = array[i];
                  array[i] = array[i+gap];
                  array[i+gap] = tmp ;
              }
          }

      }

    }

    //归并排序
    //算法思想:分治法
    //算法分析
    void mergetSort(int *array,int begin,int end)
    {
        if(begin >= end) //这个条件不能丢
            return ;
        int tmp[end-begin+1];
        int mid = begin + (end - begin)/2;
        mergetSort(array,begin,mid);
        mergetSort(array,mid+1,end);
        merge(array,begin,mid,mid+1,end,tmp);

    }

    //快速排序
    //算法思想：
    //算法分析：

    void quickSort(int *array,int begin,int end)
    {

       int i=begin ,j=end;
       if(begin >= end)
           return ;
       int base = array[i];
       while(i != j)
       {
           while(array[j] >= base && i < j)
           {
               j--;
           }

           while(array[i] <=base && i < j)//i<j条件不能丢
           {
               i++;
           }

           int tmp = array[i];
           array[i] = array[j];
           array[j] = tmp;
       }

       array[begin] = array[i];
       array[i] = base;

       quickSort(array,begin,i-1);
       quickSort(array,i+1,end);


    }

    //堆排序
    //算法思想：
    //算法分析：
    void heapSort(int *array,int begin,int end)
    {
       for(int i = end-begin+1;i>1;i--)
       {
           for(int j = i/2;j>=0;j--)
           {
               heap_adjust(array,j,i);
           }
           int tmp = array[begin];
           array[begin] = array[i-1];
           array[i-1] = tmp;
       }

    }

    //计数排序
    //算法思想：
    //算法分析:
    void countSort(int *array,int begin,int end)
    {
        int count[10] ={0};
        int index = 0;
        for(int i = begin; i <= end;++i)
        {
            count[array[i]] ++;
        }

        for(int i = 0;i<10;i++)
        {
            while(count[i])
            {
                array[index++] = i;
                count[i]--;
            }

        }
    }

    //桶排序
    //算法思想：
    //算法分析：
    void bucketSort(int *array,int begin,int end)
    {
        vector<vector<int>> v(10);
        int index = 0;

        for(int i = begin;i <= end;++i)
        {
            v[array[i]%10].push_back(array[i]);
        }

        for(vector<vector<int>>::iterator it =v.begin();it != v.end();it++)
        {
            sort(it->begin(),it->end());
        }

        for(vector<vector<int>>::iterator it =v.begin();it != v.end();it++)
        {
            for(vector<int> ::iterator it2 = it->begin();it2 != it->end();it2++)
            {
                array[index++] =  *it2;
            }


        }


    }


    //基数排序
    //算法思想:
    //算法分析：
    void radixSort(int *array,int begin,int end,int max_digit)
    {
      int mod = 10, dev =1;
      vector<vector<int>> v(10);

      for(int i = 0;i < max_digit;mod *=10,dev *=10,i++)
      {

          //排序
          for(int j = begin;j <= end;++j)
          {
              int index = array[j]%mod/dev;
              v[index].push_back(array[j]);
          }

          int index = 0;

          //放回数组
          for( vector<vector<int>>::iterator it = v.begin();it !=v.end();++it)
          {
              for(vector<int>::iterator it2 = it->begin();it2 !=it->end();++it2)
              {
                  array[index++] = *it2;
              }
              it->clear();
          }

      }
    }
private:
    void merge(int *array,int begin1,int end1,int begin2,int end2,int *tmp)
    {
       int index1 = begin1,index2 = begin2,index = begin1 ;

       while(index1 <= end1 && index2 <= end2)
       {
           if(array[index1] >= array[index2])
           {
               tmp[index++] = array[index2++];
           }
           else
           {
               tmp[index++] = array[index1++];
           }

       }

       while(index1 <= end1 )
       {
           tmp[index++] = array[index1++];
       }

        while(index2 <= end2 )
        {
            tmp[index++] = array[index2++];
        }

        memcpy(array+begin1,tmp+begin1,4*(end2-begin1+1));

    }

    void heap_adjust(int *array,int loc,int length)
    {
        int largest = loc,left = loc*2+1,right = loc*2+2;


        if(left < length && array[largest] < array[left])
        {
            largest = left;
        }

        if(right < length && array[largest] < array[right])
        {
            largest = right;
        }

        if(largest != loc)
        {
            int tmp = array[loc];
            array[loc] = array[largest];
            array[largest] = tmp;
            heap_adjust(array,largest,length);
        }


    }




};