[数据结构与算法]研发工程师面经——常见排序算法

2.排序算法

2.1 快速排序

• 快速排序的原理就是找到一个基准，然后将大于这个基准和小于这个基准的数字分别放到两边。然后不断的递归，直到只有一个元素的时候，就不用再处理。

// 在数组中交换下标为x和y的值
public static void exchange(int[] nums,int x, int y){
    int temp=nums[x];
    nums[x]=nums[y];
    nums[y]=temp;
}

public static void QuickSort(int[] nums,int left,int right){
    System.out.println(Arrays.toString(nums));
    // 选取第一个值作为基准值
    if(left<right){
        int key=nums[left];
        int i=left;
        for(int j=left+1;j<=right;j++){
            // 小于表示从大到小，大于表示从小到大
            if(key<nums[j]){
                i++;
                exchange(nums,j,i);
            }
        }
        exchange(nums,left,i);
        QuickSort(nums,left,i-1);
        QuickSort(nums,i+1,right);
    }
}

2.2 冒泡排序

• 冒泡排序是最简单，最基础的一种。就是一次遍历之后，将最大或者最小的一个放到头部或者尾部。

public static void BubbleSort(int[] array){
    for(int i=0;i<array.length;i++){
        for(int j=0;j<array.length;j++){
            if(array[j]<array[i]){
                int temp=array[i];
                array[i]=array[j];
                array[j]=temp;
            }
        }
    }
}

2.3 插入排序

• 插入排序和冒泡排序很相似。

public static void SelectSort(int[] array){
    if(array.length==0){
        return;
    }
    for(int i=0;i<array.length;i++){
        int index=i;
        for(int j=i+1;j<array.length;j++){
            if(array[index]>array[j]){
                index=j;
            }
        }
        if(i!=index){
            int temp=array[i];
            array[i]=array[index];
            array[index]=temp;
        }
    }
}

2.4 归并排序

• 归并排序是把待排序序列分为若干个子序列，每个子序 列是有序的。然后再把有序子序列合并为整体有序序列。
• 先把待排序列分为两部分，然后各部分再分为两部分，一直分下去，直到不能再分为 止，然后在两两合并两个有序数组，直到合并完为止。有序数组的合并也很好理解，代 码可以参考上面。上面代码在合并的时候都会创建一个临时数组tmp，如果排序的数组 很大的话，每次merge的时候都会浪费大量的空间，不是最好的解决方式，这里可以优化一下。

    public static void mergeSort(int[] array,int left,int right){
        if(left<right){
            int center=(left+right)>>1;
            mergeSort(array,left,center);
            mergeSort(array,center+1,right);
            merge(array,left,center,right);
        }
    }

    public static void merge(int[] data,int left,int center,int right){
        int[] tmp=new int[data.length];
        int tmpIndex=left;
        // _left表示前半段的第一个位置，_right表示后半段的第一个位置
        int _left=left;
        int _right=center+1;
        while(_left<center&&_right<=right){
            if(data[_left]<data[_right]){
                tmp[tmpIndex++]=data[_left++];
            }else {
                tmp[tmpIndex++]=data[_right++];
            }
        }
        while(_right<=right){
            tmp[tmpIndex++]=data[_right++];
        }
        while (_left<=center){
            tmp[tmpIndex++]=data[_left++];
        }
        while(left<=right){
            data[left]=tmp[left++];
        }
    }

2.5 链表排序

• 给你链表的头节点head，将其按升序排序。
• 链表排序就很复杂，因为是单向链表。
• 我的方式是：
  • 首先虚拟化头节点，然后以头节点为开头和尾节点
  • 然后选择一个指针节点，从头节点后一个节点开始遍历。
  • 小于头节点，就插入头部
  • 大于尾节点，就插入尾部
  • 大于头节点，小于尾节点，就遍历中间的链表，插入相应位置
• 注意：首先需要确保头尾节点之间的链表是独立隔离的，否则会产生环。

  public ListNode sortList(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        // 虚拟化头节点
        ListNode headNode=new ListNode();
        headNode.next=head;
        // 有序链表的尾节点
        ListNode endNode=head;
        // 起始节点node
        ListNode node=head.next;
        endNode.next=null;
        while(node!=null){
            ListNode nodeNext=node.next;
            if(node.val<=headNode.next.val){
                ListNode temp=headNode.next;
                headNode.next=node;
                node.next=temp;
            }else if(node.val>=endNode.val){
                endNode.next=node;
                node.next=null;
                endNode=node;
            }else{
                ListNode temp=headNode.next;
                while(temp!=endNode){
                    if(temp.next.val>=node.val){
                        ListNode tempNext=temp.next;
                        temp.next=node;
                        node.next=tempNext;
                        break;
                    }
                    temp=temp.next;
                }
            }
            node=nodeNext;
        }
        return headNode.next;
    }