`
univasity
  • 浏览: 809888 次
  • 性别: Icon_minigender_1
  • 来自: 广州
社区版块
存档分类
最新评论

常见排序算法 [整理]

阅读更多

 

名称 复杂度 说明 备注
冒泡排序 BubbleSort O(N*N)

将待排序的元素看作是竖着排列的 气泡 ,较小的元素比较轻,从而要往上浮


插入排序 InsertionSort O(N*N) 逐一取出元素,在已经排序的元素序列中从后向前扫描,放到适当的位置 起初,已经排序的元素序列为空
选择排序 SelcetionSort O(N*N) 首先在未排序序列中找到最小元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾。以此递归。
快速排序 QuickSort O(n*log2 (n)) 先选择中间值,然后把比它小的放在左边,大的放在右边(具体的实现是从两边找,找到一对后交换)。然后对两边分别使用这个过程(递归)。
堆排序 HeapSort O(n*log2 (n))

利用堆( heaps )这种数据结构来构造的一种排序算法。堆是一个近似完全二叉树结构,并同时满足堆属性:即子节点的键值或索引总是小于(或者大于)它的父节点。

近似完全二叉树
希尔排序 ShellSort

O(n1+ 0< <1

选择一个步长 (Step) , 然后按间隔为步长的单元进行排序 . 递归 , 步长逐渐变小 , 直至为 1.


箱排序 BinSort O(n)

设置若干个箱子,把关键字等于   k   的记录全都装入到第   k   个箱子里   (   分配   )   ,然后按序号依次将各非空的箱子首尾连接起来   (   收集   )  

分配排序的一种:通过   "   分配   "     "   收集   "   过程来实现排序。

桶排序 BucketSort O(n)

桶排序的思想是把   [0     1)   划分为   n   个大小相同的子区间,每一子区间是一个桶。

分配排序的一种:通过   "   分配   "     "   收集   "   过程来实现排序。


冒泡排序

冒泡排序算法的思想:很简单,每次遍历完序列都把最大(小)的元素放在最前面,然后再对剩下的序列重复前面的一个过程,每次遍历完之后待排序序列就少一个元素,当待排序序列减小为只有一个元素的时候排序就结束了。因此,复杂度在最坏的情况下是O(N ^ 2)。
public static void BubbleSort(int[] array){
      
      if(array==null || array.length==0){
            return;
      }
      
      int size = array.length;
      for(int i=0; i<size-1; i++){
            boolean hasSwap = false;
            for(int j=i+1; j<size; j++){
                  if(array[j]<array[i]){
                        // swap
                        int temp = array[i];
                        array[i] = array[j];
                        array[j] = temp;
                        hasSwap = true;
                  }
                  if(!hasSwap){
                        break;
                  }
            }
      }
}
 

选择排序
选择排序(Selection Sort)的基本思想是:每一趟从待排序的记录中选出关键字最小的记录,顺序放在已排好序的子文件的最后,直到全部记录排序完毕。
public static void SelectionSort(int[] array){
      
      if(array==null || array.length==0){
            return;
      }
      
      int size = array.length;
      for(int i=0; i<size-1; i++){
            int minIndex = i;
            for(int j=i+1; j<size; j++){
                  if(array[j]<array[minIndex]){
                        minIndex = j;
                  }
            }
            // 将最小值置于最前端
            if(minIndex!=i){
                  int temp = array[minIndex];
                  array[minIndex] = array[i];
                  array[i] = temp;
            }
      }
      
}
 
*与冒泡排序的区别,交换次数。每次遍历找到最小值,只交换一次。冒泡是每次比较都进行交换。

插入排序
插入排序是最简单最直观的排序算法了,它的依据是:遍历到第N个元素的时候前面的N-1个元素已经是排序好的了,那么就查找前面的N-1个元素把这第N个元素放在合适的位置,如此下去直到遍历完序列的元素为止。
  算法的复杂度也是简单的,排序第一个需要1的复杂度,排序第二个需要2的复杂度,因此整个的复杂度就是1 + 2 + 3 + …… + N = O(N ^ 2)的复杂度。
public static void InsertionSort(int[] array){
      
      if(array==null || array.length==0){
            return;
      }
      
      int size = array.length;
      // 默认认为第一位是有序的
      for(int i=1; i<size; i++){
            int key = array[i];
            // 对有序列从后向前扫描
            int j=0;
            for(j=i-1; j>=0; j--){
                  if(key<array[j]){
                        array[j+1] = array[j];
                  }else{
                        break;
                  }
            }
            array[j+1] = key;
      }
      
}
 

希尔排序
shell排序是对插入排序的一个改装,它每次排序把序列的元素按照某个增量分成几个子序列,对这几个子序列进行插入排序,然后不断的缩小增量扩大每个子序列的元素数量,直到增量为一的时候子序列就和原先的待排列序列一样了,此时只需要做少量的比较和移动就可以完成对序列的排序了。
public static void ShellSort(int array[])
{
      if(array==null || array.length==0){
            return;
      }
      
      int temp;
      int size = array.length;
      // 增量从数组长度的一半开始,每次减小一倍
      for (int increment = size / 2; increment > 0; increment /= 2)
      {
            for (int i = increment; i < size; ++i)
            {
                  temp = array[i];
                  // 对一组增量为increment的元素进行插入排序
                  int j = 0;
                  for (j = i; j >= increment; j -= increment)
                  {
                        // 把i之前大于array[i]的数据向后移动
                        if (temp < array[j - increment])
                        {
                              array[j] = array[j - increment];
                        } else
                        {
                              break;
                        }
                  }
                  // 在合适位置安放当前元素
                  array[j] = temp;
            }
      }
}
 

快速排序
快速排序的算法思想: 选定一个枢轴元素,对待排序序列进行分割,分割之后的序列一个部分小于枢轴元素,一个部分大于枢轴元素,再对这两个分割好的子序列进行上述的过程。
public static void QuickSort(int[] array, int low, int hight){
      
      if(array==null || array.length==0){
            return;
      }
      
      if(low<hight){
            int n = Partition(array, low, hight);
            QuickSort(array, 0, n);
            QuickSort(array, n+1, hight);
      }
      
}
// 对一个给定范围的子序列选定一个枢纽元素,执行完函数之后返回分割元素所在的位置,
// 在分割元素之前的元素都小于枢纽元素,在它后面的元素都大于这个元素
private static int Partition(int[] array, int low, int hight){
      
      // 采用子序列的第一个元素为枢纽元素
      int pivot = array[low];
      
      int temp = 0;
      while(low<hight){
            
            // 从后往前在后半部分中寻找第一个小于枢纽元素的元素
            while(low<hight && array[hight]>=pivot){
                  hight--;
            }
            // 将这个比枢纽元素小的元素交换到前半部分
            temp = array[low];
            array[low] = array[hight];
            array[hight] = pivot;
            
            // 从前往后在前半部分中寻找第一个大于枢纽元素的元素
            while(low<hight && array[low]<=pivot){
                  low++;
            }
            // 将这个比枢纽元素大的元素交换到后半部分
            temp = array[low];
            array[low] = array[hight];
            array[hight] = temp;
            
      }
      // 返回枢纽元素所在的位置
      return low;
}
分享到:
评论

相关推荐

    C语言常见排序算法的实现

    这里我们将深入探讨在C语言中实现的六种常见排序算法:插入排序、Shell排序、堆排序、冒泡排序、快速排序以及归并排序。 1. **插入排序**:插入排序是一种简单的排序算法,它的工作原理类似于我们日常生活中的整理...

    常见排序算法归纳整理

    以上就是8种常见排序算法的基本介绍,每种算法都有其适用场景和优缺点。C++实现使得学习者能够更直观地理解算法逻辑,并通过实际运行来验证算法的正确性。熟练掌握这些排序算法,对于提升编程能力、解决实际问题具有...

    八大排序算法整理

    ### 八大排序算法整理 #### 一、冒泡排序(交换排序) **基本思想**: 冒泡排序是一种简单的排序算法。它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地...

    java实现常见排序算法

    插入排序是一种简单直观的排序算法,它的工作原理类似于我们日常生活中整理扑克牌的过程。Java中常见的插入排序实现有三种:直接插入排序、折半插入排序和希尔排序。 1. **直接插入排序**: 直接插入排序的基本...

    排序算法整理.zip

    "排序算法整理.zip"这个压缩包文件显然包含了关于十种常见排序算法的详细资料,这些算法包括冒泡排序、选择排序、插入排序、计数排序、基数排序、堆排序、归并排序、快速排序、桶排序以及希尔排序。下面我们将逐一...

    几种排序算法整理

    本文将深入探讨由C语言实现的几种常见排序算法,包括它们的基本原理、实现细节和性能特点。 首先,让我们从最经典的排序算法——冒泡排序(Bubble Sort)开始。冒泡排序通过不断地交换相邻的不正确顺序的元素来逐步...

    七种常见VB排序算法示例程序

    在编程领域,排序算法是计算机科学中的基础概念,它用于组织和整理数据,使其按照特定顺序排列。在VB(Visual Basic)这样的编程语言中,掌握不同的排序算法可以帮助开发者编写更高效、性能更好的代码。以下是对标题...

    排序算法整理大全

    常见的基于比较的排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序等。非基于比较的排序算法,例如计数排序、基数排序、桶排序等,由于不依赖于元素间的比较操作,它们在特定条件下可以达到比...

    常见排序算法的实现

    在计算机科学领域,排序算法是数据结构与算法分析中的重要组成部分。它们用于对一组数据进行排列,以便于后续处理或优化查找效率。本项目提供了多种经典的排序算法的实现,包括冒泡排序、直接插入排序、直接选择排序...

    算法与数据结构的排序算法

    时间复杂度是衡量排序算法效率的重要指标,常见排序算法的时间复杂度如下: - 冒泡排序、插入排序、选择排序:平均和最坏情况下的时间复杂度为O(n^2)。 - 快速排序:平均时间复杂度为O(n log n),但最坏情况下为O(n^...

    常见排序算法分类与代码.rar

    这个名为"常见排序算法分类与代码.rar"的压缩包文件显然包含了多种经典的排序算法的整理和实现,主要标签包括“排序”、“冒泡”、“快速”和“直接”,这些关键词暗示了我们将讨论以下几种排序算法:冒泡排序、快速...

    最常见的几种排序算法,来看看

    这里我们将深入探讨几种最常见的排序算法,包括冒泡排序、选择排序、插入排序、快速排序以及归并排序。 1. 冒泡排序(Bubble Sort) 冒泡排序是最基础的排序算法之一,它通过不断地比较相邻元素并交换位置来实现...

    Java实现常见排序算法总结

    【Java实现常见排序算法总结】 排序算法是计算机科学中至关重要的一部分,它涉及到数据处理和算法设计。本文将探讨两种常见的排序算法在Java中的实现:直接插入排序和希尔排序。 1. **直接插入排序(直接插入排序...

    Java排序算法详细整理

    【Java排序算法详细整理】 在计算机科学中,排序算法是用于对一组数据进行排列的算法。在Java中,实现各种排序算法有助于理解数据结构和算法的原理,同时也能提高编程能力。以下是对Java中常见的几种排序算法的详细...

    常见六种排序算法的实现

    排序算法是计算机科学中用于整理一组数据的算法。下面介绍六种常见的排序算法:插入排序、shell排序、堆排序、冒泡排序、快速排序和归并排序。 插入排序(Insertion Sort)是最基础的排序算法之一。它的工作原理是...

    七种常见的VB排序算法示例程序

    本篇将详细讲解七种常见的VB排序算法及其应用。 1. 冒泡排序(Bubble Sort) 冒泡排序是最基础的排序算法,通过不断交换相邻的逆序元素来逐步实现排序。在VB中,你可以通过两个嵌套的For循环来实现这个过程,每次...

    排序算法总结.doc

    以下是对几种常见排序算法的详细说明: 1. 插入排序: 插入排序是一种简单的排序算法,其时间复杂度为O(n^2)。它通过将每个元素插入到已排序的部分中找到正确位置来工作,保持已排序部分的稳定性。当数组近乎有序...

    C#常用排序算法

    以下是四种常见的C#排序算法:冒泡排序、选择排序、插入排序和希尔排序的详细解释。 1. **冒泡排序**: 冒泡排序是一种简单的交换排序,通过重复遍历数组,比较相邻元素并根据需要交换它们的位置来完成排序。每一...

    可视化排序算法程序

    可能包含但不限于以下常见排序算法: - 冒泡排序:通过重复遍历待排序数组,比较相邻元素并交换位置来实现排序。 - 插入排序:将未排序的元素逐个插入已排序的序列中,保持序列有序。 - 选择排序:找到最小(或...

Global site tag (gtag.js) - Google Analytics