时间复杂度
f(n) 算法基本操作执行的方法
n表示算法的规模
O(n) f(n)的量级
稳定性： 同样元素的相对位置在排序前后是否有可能发生变化
冒泡排序
普冒
public class SortUtil {
public static SortService bubble = new BubbleSort();
public static SortService bubbleA = new BubbleASort();
public static void main(String[] args) {
int[] data = new int[10000];
for (int i = 0; i < data.length; i++) {
data[i] = new Random().nextInt(50000);
}
SortUtil.sort(SortUtil.bubbleA, data);
System.out.println(Arrays.toString(data));
}
private static void sort(SortService sortService, int[] data) {
long before = System.currentTimeMillis();
sortService.sort(data);
long after = System.currentTimeMillis();
System.out.println(sortService.getName() + "cost:" + (after - before));
}
}
interface SortService{
public void sort(int[] data);
public String getName();
}
class BubbleSort implements SortService{
@Override
public void sort(int[] data) {
for (int i = 0; i < data.length; i++) { // n
for (int j = 0; j < data.length - 1 - i; j++) { // n(n-1)/2
if(data[j] > data[j + 1]){ // n(n-1)/2
int temp = data[j + 1]; // n(n-1)/2
data[j + 1] = data[j]; // n(n-1)/2
data[j] = temp; // n(n-1)/2
}
}
}
}
@Override
public String getName() {
return "冒泡排序";
}
}- 耗时：170
- 时间复杂度： 最大：f(n) = n + 5*n(n-1)/2 ;O(n)=n^2 最小 f(n) = n + n(n-1)/2, O(n^2)
- 稳定
改进冒
上面的冒泡有个问题，是完全正序是复杂度过大。可以优化成如下：
class BubbleASort implements SortService {
@Override
public void sort(int[] data) {
boolean swap = true;
for (int i = 0; i < data.length; i++) { // 2
if(! swap){ // 2
break;
}
swap = false; // 1
for (int j = 0; j < data.length - 1 - i; j++) { // n
if(data[j] > data[j + 1]){ // n
int temp = data[j + 1];
data[j + 1] = data[j];
data[j] = temp;
swap = true;
}
}
}
}
@Override
public String getName() {
return "冒泡排序-改";
}
}- 耗时：会比上面慢一点
- 时间复杂度：最大差不多， 最小: f(n) = 2n + 2 + 2 + 1; O(n)
- 稳定
选择排序
/**
* 选择排序
* 把数组分割为有序区和无序区
* 从无序区中[选择出]最小/最大的放到有序区的最后
*/
class SelectSort implements SortService{
@Override
public void sort(int[] data) {
for (int i = 0; i < data.length; i++) { //n
// 选择最小数的位置的下标
int minIndex = i; // n
for (int j = i + 1; j < data.length; j++) { // n(n-1)/2
if(data[j] < data[minIndex]){ // n(n-1)/2
minIndex = j; // n(n-1)/2
}
}
int temp = data[i]; //n
data[i] = data[minIndex]; //n
data[minIndex] = temp; //n
}
}
@Override
public String getName() {
return "选择排序";
}
}- 耗时： 70 比冒泡快不少，是因为减少了数据交换的执行测试
- 时间复杂度：最坏和平均： f(n)=5n + 3n(n-1)/2 O(n^2). 最好的情况同样跟冒泡一样需要加入检测交换的情况，加入之后其复杂度为 O(n)】
- 不稳定
插入排序
普插
/**
* 插入排序
* 把数组分为左有序，右无序，初始状态左第一个为有序，后面都为无序
* 遍历无序集合，从第一个元素开始，跟有序的所有比较，找到合适位置
* 从这个位置，左部元素右移该位置插入无序集合中遍历的这个元素
*/
class InsertSort implements SortService{
@Override
public void sort(int[] data) {
for (int i = 1; i < data.length; i++) { //n
int j; //n
for (j = i - 1; j >= 0; j--) { //n(n-1)/2 因为左有序，因此找到了data[i]大于的第一个位置，就说明data[i]应该插在这个位置之后
if(data[j] < data[i]){ //n(n-1)/2，
break;
}
}
// 插入元素并后移
if(j != (i-1)){ // n
int temp = data[i]; // n
for (int k = i - 1; k > j; k--) { // n(n-1)/2
data[k + 1] = data[k]; // n(n-1)/2
}
data[j + 1] = temp; // n
}
}
}
@Override
public String getName() {
return "插入排序";
}
}- 稳定
- 耗时 63， 比选择好，是因为平均复杂度低一点，但是最坏情况比选择还要高
- 复杂度：最坏f(n)=5n + 2n(n-1) O(n^2) 平均 O(n) 最好的情况：f(n)=4n O(n)
插入排序-改
/**
* 插入排序-该
* 改前是先找插入位置，然后统一移动顺序，再插入
* 改后，使用类似冒泡的方式，在比较的同时就移动顺序
*/
class InsertSortAdvance implements SortService{
@Override
public void sort(int[] data) {
for (int i = 1; i < data.length; i++) { // n
// j是有序表尾, 连带着无序表头做冒泡
for (int j = i-1; j>=0 && data[j] > data[j+1]; j--) { // 最坏n(n-1)/2 最好 // n
int temp = data[j]; // 最坏n(n-1)/2
data[j] = data[j+1]; // 最坏n(n-1)/2
data[j+1] = temp; // 最坏n(n-1)/2
}
}
}
@Override
public String getName() {
return "插入排序";
}
}- 稳定
- 53， 因为平均中交换的操作可能执行的比较少。
- 时间复杂度 最坏：f(n) = 2n(n-1) + n O(n^2) 最好f(n)=2n O(n)
二叉树排序
/**
* 二叉树
* 先构造二叉树，构建好之后就是有序的
* 然后遍历二叉树
*/
class BinaryTreeSort implements SortService{
class Data{
int i = 0;
int[] data;
public Data(int[] data){
this.data = data;
}
public void add(int j){
data[i++] = j;
}
}
class BinaryNode{
int value;
BinaryNode left;
BinaryNode right;
public BinaryNode(int value){
this.value = value;
this.left = null;
this.right = null;
}
public void add(int value){
if(value > this.value){
if(this.right != null){
this.right.add(value);
}else{
this.right = new BinaryNode(value);
}
}else{
if(this.left != null){
this.left.add(value);
}else{
this.left = new BinaryNode(value);
}
}
}
// 中序遍历
public void iterator(Data d){
if(this.left != null){
this.left.iterator(d);
}
if(this.right != null){
this.right.iterator(d);
}
d.add(this.value);
}
}
@Override
public void sort(int[] data) {
BinaryNode n = new BinaryNode(data[0]);
for (int i = 1; i < data.length; i++) {
n.add(data[i]);
}
Data d = new Data(data);
n.iterator(d);
}
@Override
public String getName() {
return "二叉树排序";
}
}- 稳定
- cost 3
- 时间复杂度f(n) ~= nlogn + logn O(nlogn)
快速排序
/**
* 快速排序
* 选取一个元素，比其小的放在左边，比其大的放到右边
* 对于数组就是用旳第一个元素，然后从后往前比较，找到第一个比他小的，然后交换，再从前往后比较找到第一个比它大的交换，直到前后会和，完成一次分组。然后再对每个小组重新进行快排分组
*/
class QuickSort implements SortService{
@Override
public void sort(int[] data) {
quickSort(data, 0, data.length-1);
}
private void quickSort(int[] data, int low, int high) {
if(low >= high){
return;
}
int p = partition(data, low, high);
quickSort(data, low, p-1);
quickSort(data, p+1, high);
}
/**
* 得到分界线
* @param data
* @param low
* @param high
* @return
*/
private int partition(int[] data, int low, int high) {
boolean asc = false;
while(low != high){
if(asc){
if(data[low] > data[high]){
int temp = data[low];
data[low] = data[high];
data[high] = temp;
asc = !asc;
}else{
high --;
}
}else{
if(data[low] > data[high]){
int temp = data[low];
data[low] = data[high];
data[high] = temp;
asc = !asc;
}else{
low ++;
}
}
}
return low;
}
@Override
public String getName() {
return "快速排序";
}
}- 不稳定
- cost 2
- 时间复杂度 最大O(n^2) 平均O(nlogn) 最小O(nlogn)
归并排序
/**
* 归并排序
* 申请空间，使其大小为两个已排序数组之和
* 设定两个指针，起始位置为两个数组头
* 比较两个指针，选择相对小的元素放入合并空间，并移动指针到下一个位置。直到某一个指针到达末尾
* 把另一个数组的所有元素复制到合并数组的末尾
*/
class MergeSort implements SortService{
@Override
public void sort(int[] data) {
mergeSort(data, 0, data.length - 1);
int mid = data.length / 2;
// leftPart is data[]
}
private void mergeSort(int[] data, int left, int right) {
if(left >= right){
// 说明是单数组了，因此不进行分解了
return;
}
int center = (left + right)/2;
// 分解数组为左右两部分，分别排序归并
mergeSort(data, left, center);
mergeSort(data, center+1, right);
// 开始归并
merge(data, left, center, center+1, right);
}
private void merge(int[] data, int oneSortLeft, int oneSortRight, int anotherLeft, int anotherRight){
int begin = oneSortLeft;
// 用缓存来存储排序后的数据
int[] temp = new int[anotherRight + 1 - oneSortLeft];
int index = 0;
while((oneSortLeft <= oneSortRight) && (anotherLeft<=anotherRight)){
if(data[oneSortLeft] < data[anotherLeft]){
temp[index] = data[oneSortLeft];
oneSortLeft ++;
index++;
}else{
temp[index] = data[anotherLeft];
anotherLeft ++;
index++;
}
}
if(oneSortLeft <= oneSortRight){
for (int i = oneSortLeft; i <= oneSortRight; i++) {
temp[index] = data[i];
index ++;
}
}else{
for (int i = anotherLeft; i <= anotherRight; i++) {
temp[index] = data[i];
index ++;
}
}
for (int i = 0; i < temp.length; i++) {
data[i + begin] = temp[i];
}
}
@Override
public String getName() {
return "归并排序";
}
}- 稳定
- cost 3比快排慢一点点
- 时间复杂度O(nlogn)，平均最大最小都是这么多
Arrays.sort
- Java对Primitive（int，float等原型数据）数组采用快速排序，对Object对象数组采用归并排序。
- 这样是因为很多情况下对象的稳定性很重要，比如已经按照学号拍好序，想按照成绩再排一下
- 实现中快排和归并都采用递归方式，而在递归的底层，也就是递归到后面数组长度小于7时，直接使用冒泡排序，而不再递归下去。
- 这时因为当n较小的时候比较次数已经不是开销的大头，递归涉及的方法调用的开销反而会凸显
- 当数组中的元素个数较少时，源码中的阀值为7，采用的是插入排序。尽管插入排序的时间复杂度为0(n^2)，但是当数组元素较少时，插入排序优于快速排序，因为这时快速排序的递归操作影响性能。
- 快排时比较好的划分了元，比如比较小时，去前中后三个点的中间值作为元。或者更多的踩点来获得元，避免最坏情况的发生
时间： 2024-11-01 22:32:10