这五种排序算法难度依次增加。
冒泡排序:
第一次将数组相邻两个元素依次比较，然后将大的元素往后移，像冒泡一样，最终最大的元素被移到数组的最末尾。
第二次将数组的前n-1个元素取出，然后相邻两个元素依次比较，将大的元素往后移，最终n-1个元素中最大的元素又在末尾。
重复上面的步骤，直到数组只有1个元素为止。因为每次都将上一次比较剩下的最大元素放到末尾，所以当所有比较结束的时候，排序结束。
public void bubbleSort(T[] array)
{
for(int i = array.length-1;i>0; i--)
{
for(int j = 0; j <i; j++)
{
if(array[j].compareTo(array[j+1]) > 0)
{
T temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
二)选择排序
选择排序和冒泡排序类似，只是每次循环的时候将最大的元素位置记下来，然后当循环结束的时候，将最大的元素与最末尾元素进行调换。这样，当所有循环结束的时候，数组排序也结束。
@Override
public void selectionSort(T[] array)
{
for(int i = array.length-1; i>0; i--)
{
int max = 0;
for(int j = 0; j <= i; j++)
{
if(array[max].compareTo(array[j]) < 0)
{
max = j;
}
} T temp = array[max];
array[max] = array[i];
array[i] = temp;
}
}
三）插入排序
插入排序的思想是遍历整个数组，从第一个元素开始，在遍历过程中将该元素与之前元素比较，将它插入到之前元素的中间，要求是该元素大于前面所有元素，且小于等于后面所有元素。
@Override
public void insertionSort(T[] array)
{
this.insertionSort(array,0,array.length);
} @Override
public void insertionSort(T[] array, int start, int length)
{
for(int i = start; i < start+length;i++)
{
for(int j = start; j < i; j++)
{
if(array[i].compareTo(array[j]) < 0)
{
T temp = array[i];
for(int k = i; k > j; k--)
{
array[k] = array[k-1];
}
array[j] = temp;
}
}
}
}
四）希尔排序
希尔排序是插入排序的升级版。希尔排序会设置一个步长gap，然后不断减小gap，直到gap为1。而每次将数组中长度为gap的元素进行排序。其实就是先对数组进行局部排序，使得数组在总体上有序的，这样在插入排序的时候就不需要进行大规模的数据移动。
@Override
public void shellSort(T[] array)
{
int gap = array.length/2;
while(gap >=1)
{
for(int i = gap; i<array.length; i++)
{
this.insertionSort(array, i-gap, gap+1);
}
gap = gap/2;
}
}
五）快速排序
快速排序会使用到分治法和递归思想。每次排序的时候，选取一个元素，将所有小于它的元素放到左边，将所有大于它的元素放到它的右边。然后将左边和右边的元素分别看成一个数组，然后递归将剩余的元素按照之前的方式排序。当数组长度为1的时候，递归结束，整个数组排序也完成。
@Override
public void quickSort(T[] array)
{
this.quickSortInternal(array, 0, array.length-1);
} private void quickSortInternal(T[] array, int left, int right)
{
if(left >= right)
{
return;
} int _left = left;
int _right = right; boolean flag = false;
while(left!=right)
{
if(flag == false)
{
//从右向左逼近
if(array[right].compareTo(array[left]) < 0)
{
T temp = array[left];
array[left] = array[right];
array[right] = temp;
//交换后 应该调换方向
flag = !flag;
}
right--;
}
else
{
//从左向右逼近
if(array[left].compareTo(array[right]) > 0)
{
T temp = array[left];
array[left] = array[right];
array[right] = temp;
//交换后 应该调换方向
flag = !flag;
}
left++;
}
}
//递归
this.quickSortInternal(array, _left, left-1);
this.quickSortInternal(array, right+1, _right);
}
}