数组排序-冒泡排序-选择排序-插入排序-希尔排序-快速排序-Java实现

这五种排序算法难度依次增加。

冒泡排序:

第一次将数组相邻两个元素依次比较,然后将大的元素往后移,像冒泡一样,最终最大的元素被移到数组的最末尾。

第二次将数组的前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);
}
}
上一篇:【Computer Organization笔记19】层次存储器系统概述及动态存储器


下一篇:python staticmethod classmethod