排序算法之交换排序
交换排序之冒泡排序
冒泡排序算法的基本思想是:假设待排序表长为n,从后往前(或从前往后)两两比较相邻元素的值,若为逆序,则交换位置,直到序列比较完成,我们称之为一趟冒泡。如下图所示(示意下沉):( 下一趟比较时候就只需要比较到倒数第二个数字。)
Java实现如下:
public void bubbleSort2(int[] numbers){ for (int i = 0; i < numbers.length -1; i++) { boolean flag = false; for (int j = numbers.length-1; j >i ; j--) { if(numbers[j]<numbers[j-1]){ int temp = numbers[j]; numbers[j] = numbers[j-1]; numbers[j-1] = temp; flag = true; } } if (flag == false){ //flag=false 说明已经是按序排好了; return; } } }
交换排序之快速排序
快速排序是对冒泡排序的一种改进。其基本思想是基于分治法的:在待排表中任意选择一个元素standard作为基准值,通过一趟排序将待排序表划分为独立的两部分。使得左侧的小于standard值,又侧的大于standard值。(从小到大排序) 这个过程称为一趟快速排序。而后分别递归地对两个字表重复上述过程。直到每个部分只有一个元素或为空为止。一趟快排的示意图如下:
代码如下:
public void fastSort(int num[], int low, int high){ if(high > low){ int partion = partion(num, low, high); for (int i=0; i< num.length; i++){ System.out.print(num[i] + ", "); } fastSort(num, low, partion); fastSort(num, partion+1, high); } } public int partion(int num[], int low, int high){ int standard = num[low]; while (high>low){ while (num[high] >= standard && low < high){ high--; } num[low] = num[high]; while(num[low] <= standard && low < high){ low++; } num[high] = num[low]; } num[low] = standard; return low; }
两种排序的比较
空间效率:冒泡排序为O(1) ,快速排序最坏情况为O(n), 平均为O(log2n)
时间效率:冒泡排序为O(n2),快排最坏情况为O(n2),快速排序是一种不稳定第算法。
稳定性是指:在划分算法中,若有断区存在两个关键字相同,且均小于基准值,则在交换到左端区后,他们的相对位置会发生变化。