Sorting Algorithms

本文主要是介绍Sorting Algorithms，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

[TOC]

PART 1 内排序

插入排序

** 直接插入排序
**二分插入排序
**希尔排序

交换排序

** 冒泡排序
** 快速排序

---

---

交换排序

冒泡排序

基本思想：

通过无序区中相邻记录关键字间的比较和位置的交换，使关键字最小的（最大的）记录如气泡一般逐渐往上“漂浮”直至“水面”。

给出“两种”形式的冒泡，自行斟酌

大者上浮

void BubbleSort(int[] arr){int n = arr.length;for(int i = 0; i < n; i++){for(int j = 0; j < n-i-1; j++){if(arr[j]>arr[j+1]){int tmp = arr[j];arr[j] = arr[j+1];arr[j+1] = tmp;}}}
}

小者下沉

void BubbleSort(int[] arr){int n = arr.length;for(int i = 0; i < n; i++){for(int j = n-1; j > i; j--){if(arr[j]<arr[j-1]){int tmp = arr[j];arr[j] = arr[j-1];arr[j-1] = tmp;}}}
}

快速排序 ， 首先快排是由冒泡排序改进而来。

快排思想：
在待排序的n个记录中任取一个记录（通常第一个），把该记录放入适当的位置后，数据序列被划分成两份。所有关键字比该记录关键字小的记录放在前一部分，比它大的记录放置在后一部分，并把该记录放在两部分中间（称为该记录归位），这个过程称做一趟快速排序。之后对所有的两部分重复上述的过程，直至每部分内只有一个记录或空为止。

简而言之，每趟使表的第一个元素放入适当位置，将表一分为二，对子表按递归方式继续划分，直至划分的子表长度为1或0。

以第一个记录为分割点

void QuickSort(int[] arr,int low, int high){int i = low, j = high;if(low < high) {                   //至少两个元素int pivot = arr[low];         while(i!=j) {                  //while(j > i && arr[j] > pivot)   //从右向左扫描 找比pivot小的元素j--;arr[i] = arr[j];                 while(i < j && arr[i] < pivot)   //从左往右扫描i++;arr[j] = arr[i];}arr[i] = pivot;sort(arr, low, i-1);sort(arr, i+1, high);}}

Another：
以最后一个为分割点

/* This function takes last element as pivot,places the pivot element at its correctposition in sorted array, and places allsmaller (smaller than pivot) to left ofpivot and all greater elements to rightof pivot */int partition(int arr[], int low, int high) {int pivot = arr[high];int i = low -1;// index of smaller elementint tmp;if(low<high) {          for(int j = low; j < high; j++) {// If current element is smaller than or// equal to pivotif(arr[j] < pivot) {//swap arr[i] and arr[j]i++;tmp = arr[j];arr[j] = arr[i];arr[i] = tmp;}}           //swap arr[i+1] and arr[high](pivot)tmp = arr[i+1];arr[i+1] = arr[high];arr[high] = tmp;            }return i+1;}/* The main function that implements QuickSort()arr[] --> Array to be sorted,low  --> Starting index,high  --> Ending index */void sort(int[] arr, int low, int high) {/* pi is partitioning index, arr[pi] is now at right place */int pi = partition(arr, low, high);// Recursively sort elements before// partition and after partitionsort(arr, low, pi-1);sort(arr, pi+1, high);}

---

选择排序

直接选择
堆排序

直接选择

基本思想：
第i趟排序开始时，当前有序区和无序区R[0..i-1]和R[i..n-1] (0<= i =>n-1),该趟排序则是从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第一个记录R[i]交换，使R[0..i] 和 R[i+1 .. n-1]分别变为新的有序区和新的无序区，即第i趟之后，R[0..i]有序区中的关键字均小于等于R[i+1..n-1]中所有关键字，所以进行n-1趟排序后，R[0..n-2]的所有关键字小于等于R[n-1],也就是n-1趟之后，整个表R[0..n-1]递增有序。

这篇关于Sorting Algorithms的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---