Shulou(Shulou.com)06/03 Report--

Here we explain in detail the classification of the ten classic algorithms, such as exchange sort, insertion sort, selection sort and other comparison sort, as well as count sort, bucket sort and radix sort of non-comparison sort, analysis of the complexity and stability of various sort algorithms, as well as JAVA code detailed implementation. Ten algorithms such as bubble sort, insertion sort, selection sort and heap sort are summarized in detail.

1. Algorithm overview 1. Algorithm classification

Ten common sorting algorithms can be divided into two broad categories:

(1) Comparison class sorting: By comparing to determine the relative order between elements, because its time complexity can not break through O(nlogn), it is also called nonlinear time comparison class sorting.

(2) Non-comparison sort: It can break through the lower bound of time based on comparison sort without comparing the relative order between elements, and runs in linear time, so it is also called linear time non-comparison sort.

2. Algorithm complexity

3. Related concepts (1) Stability

If a comes before b and a=b, a will still come before b after sorting.

2) Unstable

If a comes before b and a=b, a may appear after b after sorting.

(3) Time complexity

The total number of operations on sorted data. Reflects what rules the number of operations presents when n changes.

(4) Spatial complexity

is a measure of the storage space required for the algorithm to execute in a computer, and is also a function of the data size n.

Second, sort algorithm code implementation 1, Bubble Sort (Bubble Sort)

Bubble sort is a simple sort algorithm. It repeatedly visits the sequence to be sorted, comparing two elements at a time and swapping them if they are in the wrong order. The work of visiting a sequence is repeated until there is no need to swap, that is, the sequence has been sorted. The algorithm gets its name from the fact that smaller elements slowly "float" to the top of the sequence by swapping.

1.1, algorithm description

(1) Compare adjacent elements. If the first is larger than the second, swap them both;

(2) Do the same for each pair of adjacent elements, from the first pair to the last pair at the end, so that the last element should be the largest number;

(3) Repeat the above steps for all elements except the last one;

Repeat steps 1 - 3 until the sorting is complete.

1.2 Code implementation (1) General implementation of Java code //general bubble sort public static void BubbleSort(int[] arr){ int temp; //temporary variable for (int i = arr.length-1;i > 0 ; i--){ //indicates the number of passes, total arr.length-1 times for (int j = 0;j

< i; j++){ // 表示比较次数,从后往前，每趟比较把最大的冒到最后面 System.out.println("第"+(arr.length-i)+"趟"+ "第"+(j+1)+"次比较"+Arrays.toString(arr)); if(arr[j] >

arr[j+1]){ temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } }(2) Optimized sorting algorithm

For the problem: After the order of the data is arranged, the bubble algorithm will continue to perform the next round of comparison until arr.length-1 times, and the latter comparison is meaningless.

Improvement scheme: Set flag bit flag to true if exchange occurs; set flag to false if no exchange occurs. In this way, if the flag is still false after a round of comparison, that is, there is no exchange in this round, indicating that the order of the data has been arranged, and there is no need to continue.

public static void BubbleSort(int[] arr){ int temp; //temporary variable boolean flag; //whether to exchange flags for (int i = arr.length-1;i > 0 ; i--){ //indicates the number of passes, total arr.length-1 times flag = false; //Set the start flag bit to false for (int j = 0;j

< i; j++){ // 表示比较次数,从后往前，每趟比较把最大的冒到最后面 System.out.println("第"+(arr.length-i)+"趟"+ "第"+(j+1)+"次比较"+Arrays.toString(arr)); if(arr[j] >

arr[j+1]){ temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; flag = true; } } if (! flag) break; }}(3) Improved cocktail bubble sorting

Improved bubble sort, cocktail bubble sort, also known as directed bubble sort, its improvement lies in the simultaneous bubbling of both sides, from low to high, and then from high to low, equivalent to the way the smallest number of bubbles to the front.

public static void cocktailSort(int[] arr){ int left = 0,right = arr.length -1,temp; while (left

< right){ for (int i = left;i < right;i++){ //将最大值冒到数组末尾 if (arr[i] >

arr[i+1]){ temp = arr[i]; arr[i] = arr[i+1]; arr[i+1] = temp; } } right--; for (int i = right;i > left;i--){ //put the smaller value before the array if (arr[i]

< arr[i-1]){ temp = arr[i]; arr[i] = arr[i-1]; arr[i-1] = temp; } } left++; }}2、选择排序(SelctionSort) 选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。 2.1、算法描述 n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下： （1）初始状态：无序区为R[1..n]，有序区为空； （2）第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区； （3）n-1趟结束，数组有序化了。 2.2、代码实现public static void selectSort(int[] arr){ //从无序的数组中选出最小值，替换到数组最前面 for(int i = 0;i < arr.length - 1;i++){ int minIndex = i; for(int j = i + 1;j < arr.length;j++){ if (arr[minIndex] >

arr[j]){ minIndex = j; } } int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; System.out.println("th"+(i+1)+"sub option"+Arrays.toString(arr)); }}2.3. Algorithm Analysis

One of the most stable sorting algorithms, because whatever data goes in is O(n2) time complexity, so the smaller the data size, the better. The only benefit is that it doesn't take up extra memory space. Theoretically speaking, selection sorting may also be the sorting method that most people think of at ordinary times.

3. Insertion Sort

The algorithm description of Insertion Sort is a simple and intuitive sorting algorithm. It works by constructing ordered sequences, scanning backward through the ordered sequence for unsorted data, finding the corresponding position and inserting.

3.1 algorithmic descriptions

In general, insert sort is implemented in-place on arrays. The algorithm is described as follows:

(1) Starting with the first element, which can be considered sorted;

(2) Take out the next element and scan from back to front in the sorted element sequence;

(3) If the element (sorted) is larger than the new element, move the element to the next position;

(4) Repeat step 3 until you find a position where the sorted element is less than or equal to the new element;

(5) Insert the new element into this position;

Repeat steps 2 - 5.

3.2 public static void insetSort(int[] arr){ for (int i = 0;i

< arr.length;i++){ for (int j = i;j >

0;j--){ //Implementation of matching exchange if (arr[j]

< arr[j-1]){ int temp = arr[j]; arr[j] = arr[j-1]; arr[j-1] = temp; }else { break; } } System.out.println("第"+(i+1)+"次插入"+Arrays.toString(arr)); }}3.3、算法分析 插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。 4、希尔排序（Shell Sort） 第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。 4.1、算法描述 先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述： （1）选择一个增量序列t1，t2，…，tk，其中ti>

tj，tk=1;

(2) sorting the sequence k times according to the increment sequence number k;

(3) For each sorting, the column to be sorted is divided into several sub-sequences with length m according to the corresponding increment ti, and each sub-table is directly inserted and sorted. Only when the increment factor is 1, the entire sequence is treated as a table, and the table length is the length of the entire sequence.

4.2 public static void ShellSort(int[] arr){ //define an incremental sequence, halving the length of the array each time int incre = arr.length; int n = 0; while (true){ n += 1; incre = incre / 2; System.out.println("+n+" th sort, increment sequence: "+incre+Arrays.toString(arr)); //Split into different array sequences according to increment, split into incre groups for (int k = 0;k

< incre; k++){ //对拆分的序列用插入排序 for (int i = k;i < arr.length;i += incre){ for (int j = i;j>

k;j-=incre){ if (arr[j]

< arr[j-incre]){ int temp = arr[j]; arr[j] = arr[j-incre]; arr[j-incre] = temp; }else { break; } } } } if (incre == 1){ break; } }}4.3、算法分析 希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版）》的合著者Robert Sedgewick提出的。 5、归并排序（Merge Sort） 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。 5.1、算法描述 （1）把长度为n的输入序列分成两个长度为n/2的子序列； （2）对这两个子序列分别采用归并排序； （3）将两个排序好的子序列合并成一个最终的排序序列。 5.2、代码实现public static int[] MergeSort(int[] arr){ if (arr.length < 2) return arr; int mid = arr.length / 2; int[] left = Arrays.copyOfRange(arr,0,mid); int[] right = Arrays.copyOfRange(arr,mid,arr.length); return merge_sort(MergeSort(left),MergeSort(right)); } public static int[] merge_sort(int[] left,int[] right){ int[] newarr = new int[left.length + right.length]; for (int index = 0,i = 0,j = 0;index < newarr.length;index++){ if (i >

= left.length){ newarr[index] = right[j++]; }else if (j >= right.length){ newarr[index] = left[i++]; }else if (left[i] > right[j]){ newarr[index] = right[j++]; }else { newarr[index] = left[i++]; } } return newarr;}5.3. Algorithm analysis

Merge sort is a stable sort method. Like selection sort, merge sort performs independently of the input data, but performs much better than selection sort because it always takes O(nlogn) time. The cost is extra memory space.

6. Quick Sort

The basic idea of quick sorting: the records to be sorted are separated into two independent parts by one sorting, in which the keywords of one part of the records are smaller than those of the other part, and the two parts of the records can be sorted separately to achieve the order of the whole sequence.

6.1, algorithm description

Quick sort uses divide and conquer to divide a list into two sub-lists. The algorithm is described as follows:

(1) Select an element from the sequence, called a "pivot";

(2) Reorder the sequence so that all elements smaller than the reference value are placed in front of the reference, and all elements larger than the reference value are placed behind the reference (the same number can be placed on either side). After this partition exits, the datum is in the middle of the series. This is called the partition operation;

(3) Recursively sort the subsequence of elements smaller than the reference value and the subsequence of elements larger than the reference value.

6.2 public static void QuickSort(int[] arr,int left,int right){ if (left >= right){ return; } //Select the first number as key int l = left,r = right; int key = arr[left]; while (l

< r){ //先从右边找到第一个小于key的数 while (l < r && key arr[l]){ l++; } if (l0;j--){ int temp = arr[0]; arr[0] = arr[j]; arr[j] = temp; //将堆顶元素与末尾元素进行交换 adjustHeap(arr,0,j); //重新进行堆调整 } } //调整堆 public static void adjustHeap(int[] arr,int i,int length){ //先取出当前元素i int temp = arr[i]; //从i结点的左子结点开始，也就是2i+1处开始 for (int k = i*2 + 1;kO(n*log(n))的时候其效率反而不如基于比较的排序，比如堆排序和归并排序和快速排序。 要求：待排序数中最大数值不能太大。 8.1、算法描述 （1）找出待排序的数组中最大和最小的元素； （2）统计数组中每个值为i的元素出现的次数，存入数组C的第i项； （3）对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）； （4）反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。 8.2、代码实现public static int[] CountSort(int[] arr){ //1、找出数组arr中的最大值 int k = arr[0]; for (int i = 1;i < arr.length;i++){ if (k < arr[i]){ k = arr[i]; } } //2、构造C数组，将A中每个元素对应C中的元素大小+1 int[] C = new int[k+1]; int sum = 0; for (int i = 0;i < arr.length;i++){ C[arr[i]] +=1; //统计A中各元素个数，对应到C数组 } //3、将C中每个i位置的元素大小改成C数组前i项和 for (int i=0;i=0;i--){ //倒序遍历A数组，构造B数组 B[C[arr[i]]-1] = arr[i]; //将A中该元素放到排序后数组B中指定的位置 C[arr[i]]--; //将C中该元素-1，方便存放下一个同样大小的元素 } //5、将排序好的数组B返回，完成排序 return B;}8.3、算法分析 计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。9、桶排序 桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。 要求：待排序数长度一致。 9.1、算法描述 （1）设置一个定量的数组当作空桶； （2）遍历输入数据，并且把数据一个一个放到对应的桶里去； （3）对每个不是空的桶进行排序； （4）从不是空的桶里把排好序的数据拼接起来。 9.2、代码实现 算法实现逻辑 （1）找出待排序数组中的最大值max、最小值min （2）我们使用 动态数组ArrayList 作为桶，桶里放的元素也用 ArrayList 存储。桶的数量为(max-min)/arr.length+1 （3）遍历数组 arr，计算每个元素 arr[i] 放的桶 （4）每个桶各自排序 （5）遍历桶数组，把排序好的元素放进输出数组 public static void BucketSort(int[] arr){ int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; for (int i = 0;i < arr.length;i++){ max = Math.max(max,arr[i]); min = Math.min(min,arr[i]); } //计算桶数 int bucketNum = (max - min) / arr.length + 1; ArrayList bunketArr = new ArrayList(bucketNum); for (int i = 0;i < bucketNum;i++){ bunketArr.add(new ArrayList()); } for (int i = 0;i>

k, so the extra space needs about n.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.