9种排序算法总结

作者: upupSue | 来源:发表于2017-05-11 17:41 被阅读351次
    各种排序算法复杂度比较

    冒泡排序

    两两比较,从底往上升。

    • 算法原理
      由最后一位开始,相邻两数两两比较,小的往上升,这样一趟下来,最小的数就被排在了第一位,第二趟也是如此,如此类推,直到所有的数据排序完成

    • c++代码实现

    void bubble_sort(int arr[], int len)
    {
          for (int i = 0; i < len - 1; i++)
          {
              for (int j = len - 1; j > i; j--)
              {
                  if (arr[j] < arr[j - 1])
                  {
                      int temp = arr[j];
                      arr[j] = arr[j - 1];
                      arr[j - 1] = temp;
                  }
              }
          }
    }
    

    选择排序

    固定位置,找元素

    • 算法原理
      • 先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置
      • 再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。
      • 以此类推,直到所有元素均排序完毕。
    • c++代码实现
      void select_sort(int arr[], int len)
      {
          for (int i = 0; i < len; i++)
          {
              int index = i;
              for (int j = i + 1; j < len; j++)
              {
                  if (arr[j] < arr[index])
                      index = j;
              }
              if (index != i)
              {
                  int temp = arr[i];
                  arr[i] = arr[index];
                  arr[index] = temp; 
              }
          }
      }
    

    插入排序

    固定元素找位置

    • 算法原理
      将数据分为两部分,有序部分与无序部分,一开始有序部分包含第1个元素,依次将无序的元素插入到有序部分,直到所有元素有序。插入排序又分为直接插入排序、二分插入排序、链表插入等,这里只讨论直接插入排序。它是稳定的排序算法,时间复杂度为O(n^2)
    • c++代码实现
      void insert_sort(int arr[], int len)
      {
          for (int i = 1; i < len; i ++)
          {
              int j = i - 1;
              int k = arr[i];
              while (j > -1 && k < arr[j] )
              {
                  arr[j + 1] = arr[j];
                  j --;
              }
              arr[j + 1] = k;
          }
      }
    

    快速排序

    挖坑填数+分治法

    • 算法原理
      • 选择一个基准元素,第一个或最后一个
      • 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分比基准小,另外一部分比基准大
      • 此时基准已经在其排好序后的位置
      • 然后再分别对这两部分数据用同样的方法进行排序,整个排序过程可以递归进行,直到整个数据变成有序序列。
        总结
        1.i =L; j = R; 将基准数挖出形成第一个坑a[i]。
        2.j--由后向前找比它小的数,找到后挖出此数填前一个坑a[i]中。
        3.i++由前向后找比它大的数,找到后也挖出此数填到前一个坑a[j]中。
        4.再重复执行2,3二步,直到i==j,将基准数填入a[i]中。
    • c++代码实现
    void quick_sort(int arr[], int left, int right)
    {
        if (left < right)
        {
            int i = left, j = right, target = arr[left];
            while (i < j)
            {
                while (i < j && arr[j] > target)
                    j--;
                if (i < j)
                    arr[i++] = arr[j];
    
                while (i < j && arr[i] < target)
                    i++;
                if (i < j)
                    arr[j] = arr[i];
            }
            arr[i] = target;
            quick_sort(arr, left, i - 1);
            quick_sort(arr, i + 1, right);
        }
    }
    

    归并排序

    • 算法原理
      假设序列共有n个元素:
      将序列每相邻两个数字进行归并操作(merge),形成floor(n/2)个序列,排序后每个序列包含两个元素
      将上述序列再次归并,形成floor(n/4)个序列,每个序列包含四个元素
      重复步骤2,直到所有元素排序完毕

    • c++代码实现

      void merge(int arr[], int temp_arr[], int start_index, int mid_index, int end_index)
      {
          int first = start_index, second = mid_index + 1;
          int index = 0;
    //比较二个数列的第一个数,谁小就先取谁,取了后就在对应数列中删除这个数,然后再进行比较,直到有数列为空,
          while (first < mid_index + 1 && second < end_index + 1)
          {
              if (arr[first] > arr[second])
                  temp_arr[index ++] = arr[second ++];
              else
                  temp_arr[index ++] = arr[first ++];
          }
     //将另一个数列的数据依次取出即可
          while (first < mid_index + 1)
          {
              temp_arr[index ++] = arr[first ++];
          }
          while (second < end_index + 1)
              temp_arr[index ++] = arr[second ++];
    
          for (i = 0, j = start_index; j < end_index + 1; i ++, j ++)
              arr[j] = temp_arr[i];
      }
    
      void merge_sort(int arr[], int temp_arr[], int start_index, int end_index)
      {
          if (start_index < end_index)
          {
              int mid_index = (start_index + end_index) / 2;
              merge_sort(arr, temp_arr, start_index, mid_index);
              merge_sort(arr, temp_arr, mid_index + 1, end_index);
              merge(arr, temp_arr, start_index, mid_index, end_index);
          }
      }
    

    堆排序

    • 算法原理(以最大堆为例)
      • 构建大顶堆
        • 初始化堆
        • 从最后一个非叶节点开始调整
        • 每次调节都从父左右节点中选最大的同父节点交换
        • 交换之后可能导致被交换的孩子节点不满足堆的性质,需要重新调整
      • 将堆顶元素通过最后一个元素 R[n] 交换
      • 由于交换后新堆顶可能违反堆的性质,因此需要重新调整为新堆,然后再次将 R[1]与无序区最后一个元素交换
    • 不断重复,直到有序区的个数为n-1
    • c++代码实现
    /**
     * 将数组arr构建大根堆
     * @param arr 待调整的数组
     * @param i   待调整的数组元素的下标
     * @param len 数组的长度
     */
    void heap_adjust(int arr[], int i, int len)
    {
        int child;
        int temp;
    
        for (; 2 * i + 1 < len; i = child)
        {
            child = 2 * i + 1;  // 子结点的位置 = 2 * 父结点的位置 + 1
            // 得到子结点中键值较大的结点
            if (child < len - 1 && arr[child + 1] > arr[child])
                child ++;
            // 如果较大的子结点大于父结点那么把较大的子结点往上移动,替换它的父结点
            if (arr[i] < arr[child])
            {
                temp = arr[i];
                arr[i] = arr[child];
                arr[child] = temp;
            }
            else
                break;
        }
    }
    /**
     * 堆排序算法
     */
    void heap_sort(int arr[], int len)
    {
        int i;
        // 调整序列的前半部分元素,调整完之后第一个元素是序列的最大的元素
        for (int i = len / 2 - 1; i >= 0; i--)
        {
            heap_adjust(arr, i, len);
        }
    
        for (i = len - 1; i > 0; i--)
        {
            // 将第1个元素与当前最后一个元素交换,保证当前的最后一个位置的元素都是现在的这个序列中最大的
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            // 不断缩小调整heap的范围,每一次调整完毕保证第一个元素是当前序列的最大值
            heap_adjust(arr, 0, i);
        }
    }
    

    希尔排序

    分组插入排序,又称缩小增量排序

    • 算法原理
      • 将整个待排元素分割成若干个序列(由相邻某个增量的元素组成)
      • 将这些序列分别进行直接插入排序
      • 缩减增量,再重复上述步骤
      • 待元素基本有序(增量足够小时)在对全体元素进行一次直接插排
    • c++代码实现
    void shellsort3(int a[], int n)  
    {  
        int i, j, gap;  
      
        for (gap = n / 2; gap > 0; gap /= 2)  
            for (i = gap; i < n; i++)  
                for (j = i - gap; j >= 0 && a[j] > a[j + gap]; j -= gap)  
                    Swap(a[j], a[j + gap]);  
    }  
    

    基数排序

    • 算法原理
      • 首先根据个位数的数值,在走访数值时将它们分配至编号0到9的桶子中
      • 接下来将这些桶子中的数值重新串接起来,成为新的数列
      • 根据十位数数值来分配,重复上述步骤
      • 续进行以上的动作直至最高位数为止
    • c++代码实现
    //最大位数
    int maxbit(int data[], int n)   
    {  
        int d = 1; //保存最大的位数  
        int p = 10;  
        for(int i = 0; i < n; ++i)  
        {  
            while(data[i] >= p)  
            {  
    ![Uploading 273973-19cf4a1e58b6ebaf_927583.png . . .]
                p *= 10;  
                ++d;  
            }  
        }  
        return d;  
    }  
    //基数排序  
    void radixsort(int data[], int n) 
    {  
        int d = maxbit(data, n);  
        int tmp[n];  
        int count[10]; //计数器  
        int i, j, k;  
        int radix = 1;  
        for(i = 1; i <= d; i++) //进行d次排序  
        {  
            for(j = 0; j < 10; j++)  
                count[j] = 0; //每次分配前清空计数器  
            for(j = 0; j < n; j++)  
            {  
                k = (data[j] / radix) % 10; //统计每个桶中的记录数  
                count[k]++;  
            }  
            for(j = 1; j < 10; j++)  
                count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶  
            for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中  
            {  
                k = (data[j] / radix) % 10;  
                tmp[count[k] - 1] = data[j];  
                count[k]--;  
            }  
            for(j = 0; j < n; j++) //将临时数组的内容复制到data中  
                data[j] = tmp[j];  
            radix = radix * 10;  
        }  
    }  
    

    计数排序

    • 算法原理
      • 遍历一遍整个数组,找出数组中最大数和最小数之间的差距 range,然后开辟一个大小为range的数组count并全部初始化为0;
      • 再次遍历整个数组,把每个元素的值映射到count的下标index(val –> (val-min)),每映射到一个index,就把count[index]加一;
      • 根据统计结果count,把数写会原数组,某个值index要写count[index]遍到原数组,这样,原数组就有序了
    • c++代码实现
    void CountSort(int *arr, int len)
    {
        assert(arr);
        if(len <= 1)
            return ;
    
        int max = arr[0];
        int min = arr[0];
     //统计数组中的最大值和最小值
        for(int i = 0; i < len; ++i)   
        {
            if(arr[i] > max)
                max = arr[i];
            if(arr[i] < min)
                min = arr[i];
        }
        int range = max + 1 - min;  //得到最大最小值的差距
        int *count = new int[range];   //用于记录数组中每个数字出现的次数 
        for(int i = 0; i < len; ++i)  // 初始化
            count[i] = 0;
    
        for(int i = 0; i < len; ++i)    
            count[ arr[i]-min ]++;  //arr[i] - min 映射到tmp中的一个下标,该下标下的值是这个数出现的次数
    
        int index = 0;
        for(int i = 0; i < range; ++i)  //再把临时数组记录的数分别拷贝到原数组中
        {
            while(count[i]--)   //每个下标下拷贝对应的次数
                arr[index++] = i + min;
        }
    } 
    

    相关文章

      网友评论

      本文标题:9种排序算法总结

      本文链接:https://www.haomeiwen.com/subject/xoootxtx.html