バブル、選択、挿入ソート

泡の順序は次のとおりです.
 

public class BubbleSort 
{
	public static void main(String[] args)
	{
		int[] array = new int[]{29, 23, 56, 40, 12, 63, 89, 7, 96, 38};
		
		System.out.println("Before sort:");
		Display(array);
		
		Sort(array);
		
		System.out.println("After sort:");
		Display(array);
	}
	
	public static void Sort(int[] array)
	{
		int temp = 0;
		for(int i=array.length-1; i>0; i--)
		{
			for(int j=0; j<i;j++)
			{
				if(array[j] > array[j+1])
				{
					temp = array[j];
					array[j] = array[j+1];
					array[j+1] = temp;
				}
			}
		}
	}
	
	public static void Display(int[] array)
	{
		for(int i=0; i<array.length; i++)
			System.out.print(array[i] + "  ");
		System.out.println();
	}
}

//*****************
// ：O(N*N)
// ：N*(N-1)/2
// ：N*(N-1)/2
//*****************

/**
Before sort:
29  23  56  40  12  63  89  7  96  38  
After sort:
7  12  23  29  38  40  56  63  89  96  
*/

 
次のようにソートを選択します.
 

public class SelectSort 
{
	public static void main(String[] args)
	{
		int[] array = new int[]{29, 23, 56, 40, 12, 63, 89, 7, 96, 38};
		
		System.out.println("Before sort:");
		Display(array);
		
		Sort(array);
		
		System.out.println("After sort:");
		Display(array);
	}
	
	public static void Sort(int[] array)
	{
		int min = 0;
		int temp = 0;
		
		for(int i=0; i<array.length-1; i++)
		{
			min = i;
			
			for(int j=i+1; j<array.length; j++)
			{
				if(array[j] < array[min])
					min = j;
			}
			
			temp = array[i];
			array[i] = array[min];
			array[min] = temp;
		}
	}
	
	public static void Display(int[] array)
	{
		for(int i=0; i<array.length; i++)
			System.out.print(array[i] + "   ");
		System.out.println();
	}
}


//*****************
// ：O(N*N)
// ：N*(N-1)/2
// ：N-1
//*****************

/**
Before sort:
29  23  56  40  12  63  89  7  96  38  
After sort:
7  12  23  29  38  40  56  63  89  96  
*/

 
 
次のようにソートを挿入します.
 

public class InsertSort 
{
	public static void main(String[] args)
	{
		int[] array = new int[]{29, 23, 56, 40, 12, 63, 89, 7, 96, 38};
		
		System.out.println("Before sort:");
		Display(array);
		
		Sort(array);
		
		System.out.println("After sort:");
		Display(array);
	}
	
	public static void Sort(int[] array)
	{
		int index = 0;
		int temp = 0;
		
		for(int i=1; i<array.length; i++)
		{
			index = i;
			temp = array[i];
			
			while(index > 0 && array[index-1] > temp)
			{
				array[index] = array[index-1];
				index--;
			}

			array[index] = temp;
		}
	}
	
	public static void Display(int[] array)
	{
		for(int i=0; i<array.length; i++)
			System.out.print(array[i] + "   ");
		System.out.println();
	}
}


//*****************
// ：O(N*N)
// ：N*(N-1)/4
// ：N-1
//*****************

/**
Before sort:
29  23  56  40  12  63  89  7  96  38  
After sort:
7  12  23  29  38  40  56  63  89  96  
*/

 
 
まとめてみます.
バブルソート、選択ソート、挿入ソートの時間的複雑さは、O(N*N)であり、いずれも安定である.選択したソートの比較回数はバブルソートの比較回数と同様に,いずれもN*(N−1)/2であったが,交換回数はそれより少なかった(N−1回とN*(N−1)/2回).挿入ソートの比較回数は、バブルソートよりも2倍速く、選択ソートよりもやや速い.要するに、比較的、挿入ソートが速い.