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