本章假定：1）要排序的数据是整数 2）数据存储在数组中 3）排序结果按照升序排列
1.选择排序
- 每次假设未排序的数字中第一个数最小，然后拿后面的数字比较，找出最小的，如果不是第一个数字，就和第一个交换，保证一次一个最小的数字。
public class text6_选择排序 {
public void selectSort(int []list){
for(int i=0;i<list.length-1;i++){
int min=list[i];
int min_index=i;
for(int j=i+1;j<list.length;j++){
if(list[j]<min){
min=list[j];
min_index=j;
}
}
if(min_index!=i){
list[min_index]=list[i];
list[i]=min;
}
}
}
@Test
public void test(){
int []list={2,3,2,5,6,1,-2,3,14,12};
selectSort(list);
for(int i=0;i<list.length;i++)
System.out.print(list[i]+" ");
}
}
2.插入排序
- 插入第p个元素，保证从位置0到位置p-1是已排序的状态。
-
插入时，依次比较arr[p-1]...与要插入元素arr[p]的大小，如果大于要插入的元素arr[p],就往后移动一位，直到找到比当前要插入元素小的元素的位置K，将要插入的元素插入到K+1的位置。
private void insertSort(int[] array){
//p表示要插入的元素位置
for(int p=1;p<array.length;p++){
int current=array[p];
//和前p-1个元素比较，找到大于等于左边，小于右边的插入位置
int i;
for(i=p-1;i>=0&&array[i]>current;i--){
//如果元素比要插入的元素大，就往后移一位
array[i+1]=array[i];
}
//比较完了之后，i索引要么<0,要么array[i]<current
//插入位置i+1
array[i+1]=current;
}
}
- 插入排序算法复杂度 O（n的平方）
3.冒泡排序
每次遍历时，比较连续相邻的元素，如果某一对元素是降序，则互换他们的值；否则保持不变。较大的值像气泡一样逐渐浮向顶部，第一次遍历之后，最后一个元素成为数组中的最大数。第二次遍历倒数第二个元素成为数组中的第二大数。
private void BubbleSort(int[] array) {
boolean neddNextPass = true;
//i是负责遍历次数的，6个数字只需要5次遍历
for (int i = 0; i < array.length - 1 && neddNextPass; i++) {
//如果走了一圈，没有发生交换事件，说明顺序排好了，不需要进行下一次大遍历
neddNextPass=false;
for (int j = 0; j < array.length - 1 - i; j++) {
//j负责一次遍历中的交换
if (array[j] > array[j + 1]) {
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
neddNextPass = true;
}
}
}
}
-
在最佳的情况下，冒泡只需要进行一次遍历确定数组已经排好序，不需要进行下一次遍历。由于第一次排序比较次数是n-1，因此在最佳情况下，冒泡时间复杂度O(n)
4.归并排序
- 递归的进行拆分合并：条件array.length()>1,将数组拆成一个一个元素，并排序后再合并
public class text3_归并排序 {
public void mergeSort(int[] array){
if(array.length>1){
//将左半边存到firstHalf数组中
int firstHalf[]=new int[array.length/2];
System.arraycopy(array,0,firstHalf,0,array.length/2);
//左半边递归
mergeSort(firstHalf);
//将右半边存到secondHalf数组中
int seconHalfLength=array.length-array.length/2;
int secondHalf[]=new int[seconHalfLength];
System.arraycopy(array,array.length/2,secondHalf,0,seconHalfLength);
//右半边递归
mergeSort(secondHalf);
//排序合并
merge(firstHalf,secondHalf,array);
}
}
private void merge(int[] firstHalf, int[] secondHalf, int[] array) {
int firstHalf_index=0;
int secondHalf_index=0;
int array_index=0;
//如果左边索引值小于左边数组长度，并且右边索引值小于右边数组长度，比较左右两边依次把小的数放入array数组中
while (firstHalf_index<firstHalf.length&&secondHalf_index<secondHalf.length){
if(firstHalf[firstHalf_index]<secondHalf[secondHalf_index])
//左边小于右边，左边的数放到array中，左边索引值+1
array[array_index++]=firstHalf[firstHalf_index++];
else
array[array_index++]=secondHalf[secondHalf_index++];
}
//如果右边排完了，左边还剩着
while(firstHalf_index<firstHalf.length)
array[array_index++]=firstHalf[firstHalf_index++];
while (secondHalf_index<secondHalf.length)
array[array_index++]=secondHalf[secondHalf_index++];
}
@Test
public void test(){
int []list={2,3,2,5,6,1,-2,3,14,12};
mergeSort(list);
for(int i=0;i<list.length;i++)
System.out.print(list[i]+" ");
}
}
5.快速排序
public class text4_快速排序 {
private void quickSort(int[] list){
quickSort(list,0,list.length-1);
}
private void quickSort(int[] list, int first, int last) {
if(last>first){
int pivotIndex=partition(list,first,last);
quickSort(list,0,pivotIndex-1);
quickSort(list,pivotIndex+1,last);
}
}
private int partition(int[] list, int first, int last) {
//以第一个数为主元
int pivot=list[first];
int low=first+1;
int high=last;
while(low<high){
//low从左到右找比主元大的数的指针
while(low<=high&&list[low]<=pivot)
low++;
//high从右到左找小于等于主元的数的指针
while (low<=high&&list[high]>pivot)
high--;
//找到两个值后，交换，目的是把比主元小的放到左边，大的放在右边
if(low<high)
{
int tmp=list[low];
list[low]=list[high];
list[high]=tmp;
}
}
//直到low>=high跳出循环
//high指针向左移，找到第一个小于主元的值，将主元和该值互换
while(high>first&&list[high]>=pivot)
high--;
if(list[high]<pivot)
{
list[first]=list[high];
list[high]=pivot;
return high;
}
else
return first;
}
@Test
public void test(){
int []list={2,3,2,5,6,1,-2,3,14,12};
quickSort(list);
for(int i=0;i<list.length;i++)
System.out.print(list[i]+" ");
}
}
6.堆排序
1）二叉堆是具有如下属性的二叉树
- 形状属性：是一颗完全二叉树
-
堆属性：每个结点大于或等于它的任意一个孩子。
完全二叉树：
图片.png
2）堆的相关算法分析
-
堆的存储
-
添加一个新的节点
-
删除根节点
原始堆
删除根节点过程：
3）Heap类的设计与实现
public class Heap<E extends Comparable<E>> {
private ArrayList<E> list=new ArrayList<E>();
public Heap(){}
public Heap(E[] object) {
for(int i=0;i<object.length;i++)
add(object[i]);
}
//添加的元素先放到最后一个位置，如果比父元素大，就和父元素交换
//如果比父元素小，就是找到位置，跳出
public void add(E newObject) {
list.add(newObject);
int currentIndex=list.size()-1;
while (currentIndex>0){
//如果当前节点的值比父节点大，就要和父节点交换
int parentIndex=(currentIndex-1)/2;
if(list.get(currentIndex).compareTo(list.get(parentIndex))>0){
E tmp=list.get(parentIndex);
list.set(parentIndex,list.get(currentIndex));
list.set(currentIndex,tmp);
}else
break;
currentIndex=parentIndex;
}
}
public E remove(){
if(list.size()==0)return null;
E removeObject=list.get(0);
//将根元素设置为最后一个
list.set(0,list.get(list.size()-1));
list.remove(list.size()-1);
int currentIndex=0;
//重建堆的过程：
//就是要让根元素大于孩子元素，先找到孩子元素中最大的值，和根元素比较，比根元素大，就交换。
//找不到就跳出
//找出左右孩子较大的元素
while(currentIndex<list.size()){
int leftChildIndex=2*currentIndex+1;
int rightChildIndex=2*currentIndex+2;
//如果左孩子超出范围，结束
if(leftChildIndex>=list.size())
break;
//找出左右孩子中较大数的索引
int maxIndex=leftChildIndex;
if(rightChildIndex<list.size()){
if(list.get(maxIndex).compareTo(list.get(rightChildIndex))<0){
maxIndex=rightChildIndex;
}
}
//当前元素比左右孩子中较大的小，和较大的孩子换位置
if(list.get(currentIndex).compareTo(list.get(maxIndex))<0)
{
E temp=list.get(currentIndex);
list.set(currentIndex,list.get(maxIndex));
list.set(maxIndex,temp);
currentIndex=maxIndex;
}
//当前元素已经最大了
else
break;
}
return removeObject;
}
public int getSize(){
return list.size();
}
}
4) HeapSort堆排序
也就是调用remove()方法，每次返回的都是最大值
public class HeapSort {
public static <E extends Comparable<E>> void heapSort(E[] list){
Heap<E> heap=new Heap<E>(list);
for(int i=list.length-1;i>=0;i--){
list[i]=heap.remove();
}
}
public static void main(String[] args){
Integer[] list={-44,-5,-3,3,3,1,-4,0,1,2,4,5,53};
heapSort(list);
for(int i=0;i<list.length;i++)
System.out.print(list[i]+" ");
}
}
7.外部排序
如果需要对存储在外部文件中的数据排序，首先要将数据送入内存，然后对它们进行内部排序。然而，如果文件太大，那么文件中的所有数据不能同时送入内存。如何在大型外部文件中对数据排序，称为外部排序。
