算法排序【时间复杂度O(n^2)】

排序算法的两个原则:

1.输出结果为递增或者递减。

2.输出结果为原输入结果的排列或者重组。

平均时间复杂度为O(n^2)的排序算法有三种:

冒泡排序,插入排序,选择排序。

一。冒泡排序:

即谁冒泡泡冒得快,上升的就快。

 /*冒泡排序 复杂度O(n^2)
* 1.比较相邻的元素。如果第一个比第二个大,就交换他们两个。
2.对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
3.针对所有的元素重复以上的步骤,除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
*/
public int[] BubblingSort(int[] arr)
{
int temp = 0;
boolean unsort = true; while(unsort)
{
for(int i=0;i<arr.length;i++)
{
if(arr[i]>arr[i+1])
{
temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
unsort = true;
}
}
}
return arr;
}

冒泡排序平均时间复杂度为O(n^2)。

二。插入排序

工作原理是通过构建有序序列,对于未排序的数据,在已排序的序列中从后向前扫描,找到相应位置并插入。

主要有两个动作:操作和交换。

 /*插入排序 默认第一个元素是已被排序
* 取出下一个元素 在已排序的元素中进行比较
* 如果已排序的元素大于该元素 则将该元素移动到下一位置
* 直到找到小于或等于的该元素的位置
* 将该元素插入到该位置
* 如果比较操作的代价大于交换操作的话 就要考虑用二分查找法
* 最差复杂度O(N^2) 最优时间复杂度O(N) 平均时间复杂度O(N^2) 空间复杂度O(N)
* 和冒泡排序是一个级别
*/
public void insertSort(int[] data)
{
int temp = 0;
for(int i=1;i<data.length;i++)
{
for(int j=i;(j>0)&&(data[j]<data[j-1]);j--)
{
temp = data[j-1];
data[j-1] = data[j];
data[j] = temp;
}
}
}

三,选择排序

在未排序序列中找到最小元素,存放在排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小最小元素,然后放到排序序列的末尾。以此类推,知道所有元素均排序完毕。

 /*选择排序:首先在未排序的元素中找到最小的元素 放在排序序列的起始位置
* 然后在从生下的序列元素中继续找到最小元素,然后放在已排序序列的末尾
* 复杂度O(N^2)*/
public void selectionSort(int[] array)
{
int i,j;
int temp;
for(i=0;i<array.length-1;i++)
{
int min = i;
for(j=i+1;j<array.length;j++)
{
if(array[min] > array[j])
{
min=j;
}
} temp = array[min];
array[min] = array[i];
array[i] = temp; }
}
上一篇:安装使用swoole


下一篇:js将字符串转换为数字等类型