名称
|
复杂度
|
说明
|
备注
|
冒泡排序 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语言中实现的六种常见排序算法:插入排序、Shell排序、堆排序、冒泡排序、快速排序以及归并排序。 1. **插入排序**:插入排序是一种简单的排序算法,它的工作原理类似于我们日常生活中的整理...
以上就是8种常见排序算法的基本介绍,每种算法都有其适用场景和优缺点。C++实现使得学习者能够更直观地理解算法逻辑,并通过实际运行来验证算法的正确性。熟练掌握这些排序算法,对于提升编程能力、解决实际问题具有...
### 八大排序算法整理 #### 一、冒泡排序(交换排序) **基本思想**: 冒泡排序是一种简单的排序算法。它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地...
插入排序是一种简单直观的排序算法,它的工作原理类似于我们日常生活中整理扑克牌的过程。Java中常见的插入排序实现有三种:直接插入排序、折半插入排序和希尔排序。 1. **直接插入排序**: 直接插入排序的基本...
"排序算法整理.zip"这个压缩包文件显然包含了关于十种常见排序算法的详细资料,这些算法包括冒泡排序、选择排序、插入排序、计数排序、基数排序、堆排序、归并排序、快速排序、桶排序以及希尔排序。下面我们将逐一...
本文将深入探讨由C语言实现的几种常见排序算法,包括它们的基本原理、实现细节和性能特点。 首先,让我们从最经典的排序算法——冒泡排序(Bubble Sort)开始。冒泡排序通过不断地交换相邻的不正确顺序的元素来逐步...
在编程领域,排序算法是计算机科学中的基础概念,它用于组织和整理数据,使其按照特定顺序排列。在VB(Visual Basic)这样的编程语言中,掌握不同的排序算法可以帮助开发者编写更高效、性能更好的代码。以下是对标题...
常见的基于比较的排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序等。非基于比较的排序算法,例如计数排序、基数排序、桶排序等,由于不依赖于元素间的比较操作,它们在特定条件下可以达到比...
在计算机科学领域,排序算法是数据结构与算法分析中的重要组成部分。它们用于对一组数据进行排列,以便于后续处理或优化查找效率。本项目提供了多种经典的排序算法的实现,包括冒泡排序、直接插入排序、直接选择排序...
时间复杂度是衡量排序算法效率的重要指标,常见排序算法的时间复杂度如下: - 冒泡排序、插入排序、选择排序:平均和最坏情况下的时间复杂度为O(n^2)。 - 快速排序:平均时间复杂度为O(n log n),但最坏情况下为O(n^...
这个名为"常见排序算法分类与代码.rar"的压缩包文件显然包含了多种经典的排序算法的整理和实现,主要标签包括“排序”、“冒泡”、“快速”和“直接”,这些关键词暗示了我们将讨论以下几种排序算法:冒泡排序、快速...
这里我们将深入探讨几种最常见的排序算法,包括冒泡排序、选择排序、插入排序、快速排序以及归并排序。 1. 冒泡排序(Bubble Sort) 冒泡排序是最基础的排序算法之一,它通过不断地比较相邻元素并交换位置来实现...
【Java实现常见排序算法总结】 排序算法是计算机科学中至关重要的一部分,它涉及到数据处理和算法设计。本文将探讨两种常见的排序算法在Java中的实现:直接插入排序和希尔排序。 1. **直接插入排序(直接插入排序...
【Java排序算法详细整理】 在计算机科学中,排序算法是用于对一组数据进行排列的算法。在Java中,实现各种排序算法有助于理解数据结构和算法的原理,同时也能提高编程能力。以下是对Java中常见的几种排序算法的详细...
排序算法是计算机科学中用于整理一组数据的算法。下面介绍六种常见的排序算法:插入排序、shell排序、堆排序、冒泡排序、快速排序和归并排序。 插入排序(Insertion Sort)是最基础的排序算法之一。它的工作原理是...
本篇将详细讲解七种常见的VB排序算法及其应用。 1. 冒泡排序(Bubble Sort) 冒泡排序是最基础的排序算法,通过不断交换相邻的逆序元素来逐步实现排序。在VB中,你可以通过两个嵌套的For循环来实现这个过程,每次...
以下是对几种常见排序算法的详细说明: 1. 插入排序: 插入排序是一种简单的排序算法,其时间复杂度为O(n^2)。它通过将每个元素插入到已排序的部分中找到正确位置来工作,保持已排序部分的稳定性。当数组近乎有序...
以下是四种常见的C#排序算法:冒泡排序、选择排序、插入排序和希尔排序的详细解释。 1. **冒泡排序**: 冒泡排序是一种简单的交换排序,通过重复遍历数组,比较相邻元素并根据需要交换它们的位置来完成排序。每一...
可能包含但不限于以下常见排序算法: - 冒泡排序:通过重复遍历待排序数组,比较相邻元素并交换位置来实现排序。 - 插入排序:将未排序的元素逐个插入已排序的序列中,保持序列有序。 - 选择排序:找到最小(或...