436
京东网上商城
几种排序算法整理
一、选择排序
public class SelectSort{
/**
*选择排序基本思想：
*首先，将一个序列中的最小值与第一个值交换；
*第二轮，将剩下n-1个值组成的序列中的最小值与第二个值交换；
*直至交换完全。
*时间复杂度为O(n2),空间复杂度O(1),因为只使用了一个辅助变量，且是在原记录数据上进行操作的。
*@param unordered 一个无序列表(为简单起见，假设为整型数组)。
*/
public static void main(String[] args) {
int test[]={1,3,2,6,4,5,10,9,8,10,7,11};
for(int i:test)
{
System.out.print(i+" ");
}
System.out.println();
selectSort(test);
for(int j:test)
{
System.out.print(j+" ");
}
}
static void selectSort(int unordered[])
{
int len = unordered.length;
int temp,j;
for(int i=0;i<len-1;i++)
{
j=i;
for(int k=i+1;k<len;k++)
{
if(unordered[k]<unordered[j])
{
j=k; //如果有比第一个还小的，则将j指向较小的那个，最后j将指向最小的那个
}
}
if(i!=j) //j有变动才交换，无变动不交换
{
temp=unordered[j];
unordered[j]=unordered[i];
unordered[i]=temp;
}
}
}
}
二、插入排序
public class InsertSort{
public static void main(String[] args) {
InsertSort is = new InsertSort();
int test[]={1,3,2,6,4,5,10,9,8,10,7,11};
for(int i:test)
{
System.out.print(i+" ");
}
System.out.println();
is.insertSort(test);
for(int j:test)
{
System.out.print(j+" ");
}
}
/**
*插入排序基本思想：
*将一组数列看做是一个有序数列和一个无序数列的组合，每次在有序数列中插入一个数，使之仍然为有序数列。
*时间复杂度为O(n2),空间复杂度O(1),因为只使用了一个辅助变量，且是在原记录数据上进行操作的。
*@param unordered 一个无序列表(为简单起见，假设为整型数组)。
*/
void insertSort(int unsorted[])
{
int len=unsorted.length;
int j,temp;
for(int i=1;i<len;i++)
{
if(unsorted[i]<unsorted[i-1])
{
temp=unsorted[i];
for(j=i-1;temp<unsorted[j];j--) //将比较条件放在for循环里面，一旦发现有比有序序列小的数，则进行一次插入排序
unsorted[j+1]=unsorted[j];
unsorted[j+1]=temp;
}
}
}
}
三、冒泡排序
public class BubbleSort{
public static void main(String[] args) {
BubbleSort bs = new BubbleSort();
int test[]={1,3,2,6,4,5,10,9,8,10,7,11};
for(int i:test)
{
System.out.print(i+" ");
}
System.out.println();
bs.bubbleSort(test);
for(int j:test)
{
System.out.print(j+" ");
}
}
/**
*冒泡排序的基本思想：
*通过将数组中的相邻数字进行两两比较，将较大的沉底，较小的浮出水面。
*时间复杂度为O(n2),空间复杂度O(1),因为只使用了一个辅助变量，且是在原记录数据上进行操作的。
*@param unsorted[] 一个无序数组，假定为整型数组。
*/
void bubbleSort(int unsorted[])
{
int len = unsorted.length;
int temp;
for(int i=0;i<len;i++)
{
for(int j=i;j<len-1;j++)
{
if(unsorted[j+1]<unsorted[j])
{
temp=unsorted[j];
unsorted[j]=unsorted[j+1];
unsorted[j+1]=temp;
}
}
}
}
}
最后更新：2017-04-24 00:00:33