排序算法学习小结

排序算法小结

• 冒泡排序：它是一种简朴的排序算法，通过重复地走访要排序的数列，一次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地举行直到没有再须要交换，也就是说该数列已经排序完成。这个算法的名字由来是由于越小的元素会经由交换慢慢 “浮” 到数列的顶端，就像气泡上升一样，其时间复杂度为O(n²)，是稳固的排序算法。
  
• 插入排序：插入排序的工作原理是对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。就像打扑克牌时，每次拿到一张新牌，都会将其插入到手中已有的有序牌中的符合位置，时间复杂度为O(n²)，是稳固的排序算法。
  
• 选择排序：选择排序首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继承探求最小（大）元素，然后放到已排序序列的末端。以此类推，直到全部元素均排序完毕，时间复杂度为，是不稳固的排序算法。
  
• 快速排序：快速排序接纳分治战略，先从数列中挑出一个元素作为基准值，将数列中比基准值小的元素都移到基准的左边，比基准值大的元素都移到基准的右边，然后对左右两个子数列分别重复上述操作，直到每个子数列只有一个元素，此时整个数列就有序了。均匀时间复杂度为O(n log n)，但最坏情况会退化为O(n²)，是不稳固的排序算法。
  
• 归并排序：归并排序是把待排序的序列分成若干个长度为 1 的子序列，然后将这些子序列两两合并，得到若干个长度为 2 的有序子序列，再将这些长度为 2 的子序列两两合并，得到若干个长度为 4 的有序子序列，以此类推，直到最终合并成一个长度为 n 的有序序列。其时间复杂度始终为O(n log n)，是稳固的排序算法，但须要额外的空间来举行合并操作，空间复杂度为O(n)。
  

排序算法时间复杂度（最好）时间复杂度（均匀）时间复杂度（最坏）空间复杂度稳固性冒泡排序O(n)O(n²)O(n²)O(1)稳固插入排序O(n)O(n²)O(n²)O(1)稳固选择排序O(n²)O(n²)O(n²)O(1)不稳固快速排序O(n log n)O(n log n)O(n²)最好O(log n)，最坏O(n)不稳固归并排序O(n log n)O(n log n)O(n log n)O(n)稳固 稳固性：相等元素的相对顺序是否保持稳定，比如说数组中有5个5，这5个5的相对顺序不会发生改变。
冒泡排序

在一开始打比赛的时间不会用语言自带的sort排序,自己直接手敲了个冒泡排序。
第一层for循环是对第二层for循环的次数,第二层for循环是从数组的开始到竣事，举行两两比较巨细，大的放在背面，第二层循环之后，肯定可以找到最大的数，并且最大的数在数组的尾部。

1. public static int[] bubbleSort(int[] arr, int size) {
2.        for (int i = 0; i < size-1; i++) {//下面j的循环次数
3.            for (int j = 0; j < size-i-1; j++) {
4.                if (arr[j] > arr[j+1]) {//前面大，则进行交换
5.                    arr[j] = arr[j]^arr[j+1];
6.                    arr[j+1] = arr[j]^arr[j+1];
7.                    arr[j] = arr[j]^arr[j+1];
8.                }
9.            }
10.        }
11.        return arr;
12.    }

复制代码

插入排序

插入排序，排序的逻辑和名字相同，插入已经排序好的数组，首先，把排序好的数组的值最右边+1的值赋给temp，这个temp现在属于未排序的，然后while 循环从右到左遍历已经排序好的数组，当temp的值小于比较的值时，比较的值向右移动一位，temp值向左，直到遇见大于的值，大于的值直接插入。下面i!=j是举行赋值的，当i=j时就刚好temp值比排序好的数组最大值还要大。

1. public static int[] insertionSort(int[] arr,int size) {
2.        int temp;
3.        for (int i = 1; i < size ; i++) {
4.            temp = arr[i];
5.            int j = i;
6.            while ( j > 0 && arr[j-1] > temp) {
7.                arr[j]= arr[j-1];
8.                j--;
9.            }
10.            if (i!=j){
11.                arr[j] = temp;
12.            }
13.        }
14.        return arr;
15.    }

复制代码

选择排序

感觉和冒泡差不多，每次选择最小值，把最小值和i所在的值举行交换。

1. for (int i = 0; i <size-1 ; i++) {
2.            int min =i;
3.            for (int j = i+1; j < size; j++) {
4.                if (arr[j] < arr[min]) {
5.                    min=j;
6.                }
7.            }
8.            if (min != i) {
9.                arr[min] = arr[min]^arr[i];
10.                arr[i] = arr[min]^arr[i];
11.                arr[min] = arr[min]^arr[i];
12.            }
13.        }

复制代码

快速排序

快速排序，找基准值，把比基准值小的数放在基准值的左边，比基准值大的数放在右边， 下面代码，由i，j两个指针去走，如果找到arr比基准值大，停，如果找到arr[j]比基准值大,停，交换arr和arr[j]的值, 大致分为双方，左边是比基准值小的，右边是大的，末了把基准值和arr举行交换,arr肯定是小于即是基准值的，这时基准值就在中间了， 而左边也是小于基准值的，右边也是大于基准值的。 快速一轮找到基准值小的，和基准值大的，再分成两个组开始下去找，直到左即是右

1. static void quickSort(int[] arr, int left, int right) {
2.        if(left >= right){
3.            return ;
4.        }
5.        int partitionIndex  = partition(arr, left, right);
6.        quickSort(arr, left, partitionIndex - 1);
7.        quickSort(arr, partitionIndex+1, right);
8.        return ;
9.    }
10.    static int partition(int[] arr, int left, int right) {
11.        int i =left;
12.        int j =right;
13.        while(i<j){
14.            while(i<j && arr[j] >= arr[left])
15.                j--;
16.            while (i<j && arr[i] <= arr[left])
17.                i++;
18.            swap(arr, i, j);
19.        }
20.        swap(arr, i,left);
21.        return i;
22.    }
23.    static void swap(int[] arr, int i, int j) {
24.        int temp = arr[i];
25.        arr[i] = arr[j];
26.        arr[j] = temp;
27.    }

复制代码

归并排序

归并往下递归直到左即是右，左即是右返回，两个数比较，合并，再返回，四个数比较，合并，返回，依次类推末了完成排序，和快排差别的是，它是先探索到底，然后，逐级比较合并返回到上面。快速则一开始就分左右，探到底则完成排序。

1. static void mergeSort(int left, int right) {
2.        if(left >= right){
3.            return;
4.        }
5.        int mid = left + (right - left)/2;
6.        mergeSort(left, mid);
7.        mergeSort(mid + 1, right);
8.        merge(left, mid, right);
9.    }
10. ​
11.    //合并
12.    static void merge(int left, int mid, int right) {
13.        //确保三个值不要变
14.        int[] temp = new int[right - left + 1];
15.        int i = left, j = mid + 1, k = 0;
16.        while (i <= mid && j <= right) {
17.            if (arr[i] <= arr[j]) {
18.                temp[k++] = arr[i++];
19.            }
20.            else {
21.                temp[k++] = arr[j++];
22.            }
23.        }
24. ​
25.        //i没走完，把i剩余的数放入临时数组
26.        while (i <= mid) {
27.            temp[k++] = arr[i++];
28.        }
29. ​
30.        //j没走完，把j剩余的数放入临时数组
31.        while (j <= right) {
32.            temp[k++] = arr[j++];
33.        }
34. ​
35.        //将数组一一替换成已经排序好的临时数组
36.        for (k=0;k<temp.length;k++) {
37.            arr[left+k] = temp[k];
38.        }
39.    }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。