Java排序算法

滴滴面试测试开发提到问题

1.前几家公司辞职的理由
2.代码：编辑程序将一组无序的数组分成奇偶两组并按顺序排序
3.朋友圈的点赞功能，写测试用例
4.说说目前的项目中测试主要涉及的方面
5.对我们有什么想要了解的吗

Java代码编写排序

• 冒泡排序

1.相邻的两个数据作比较，找出最小值，最小排列在前
2.循环执行，直到下一个数值始终大于前一个数值

void  bullbleSort(){
         int len = a.length;
         for (int i=0; i<len;i++){
             for (int j=0; j<len-1-i;j++){
                 if (a[j]>a[j+1]){
                     int temp = a[j];
                     a [j] = a[j+1];
                     a[j+1] = temp;
                 }
             }
         }
         System.out.println(Arrays.toString(a));
    }

• 选择排序

1.数值分区为已经排序（0，i-1）和未排序（i，n）
2.从未排序的中数组中找到最小的minIndex，将最小数值与i交换
3.循环执行

void selectSort(){
         int len = a.length;
         for (int i =0;i < len; i++){
             int minindex = i;
             for (int j=i+1; j<len ; j++){
                 if (a[j]< a[minindex]){
                     minindex = j;
                 }
                 int temp = a[j];
                 a[j] = a[minindex];
                 a[j] = temp;
             }
         }
         System.out.println(Arrays.toString(a));
    }

• 插入排序

1.分为已经排序的和未排序的两个部分
2.取未排序的值，向前比较，如果已排序的数大于未排序的元素，已经排序的index+1
3.直到取到已经排序的元素小于等于新的元素，新元素插入这个元素后边
4.循环

void insertSort(){
        int len = a.length;
        int preIndex, current;
        for (int i =1 ;i<len; i++){
            preIndex = i - 1;
            current = a[i];
            while (preIndex >=0&& a[preIndex] > current){
                a[preIndex+1] = a[preIndex];
                preIndex--;
            }
            a[preIndex+ 1] = current;
        }
        System.out.println(Arrays.toString(a));
    }

}

• 快速排序法
  1.选一个基准，比如选第一个数为基准
  2.将数据大于它的放在右边，小于的放在左边
  3.递归排序左右两边的数据

int mpartition(int a[], int l, int r) {
int pivot = a[l];

while (l<r) {
    while (l<r && pivot<=a[r]) r--;
    if (l<r) a[l++]=a[r];
    while (l<r && pivot>a[l]) l++;
    if (l<r) a[r--]=a[l];
}
a[l]=pivot;
return l;

}

void quick_sort (int a[], int l, int r) {

if (l < r) {
    int q = mpartition(a, l, r);
    msort(a, l, q-1);
    msort(a, q+1, r);
}

}