Java Algorithm (1)—Primary Sorting Algorithm

Program = data structure + algorithm. For those frameworks that build projects that are not written by us, what can really judge the level of a project is whether the data structures we customize are convenient, concise, and low-coupled; whether the algorithms we use to implement these methods are fast and effective. , less error-prone. If what you want to do is not the kind of job of moving bricks from morning to night every day, learning algorithms and analyzing data structures is definitely the only way for you to increase your level.

(1) Sorting algorithm

Algorithms and programming languages ​​are closely related, but they are not only dependent on a certain language. Without considering the implementation language, we usually have the following sorting methods:

1. Selection sort

2. Insertion sort

3. Hill sort

4. Merge sort

5. Quick sort

We are not just talking about these sorting methods in general. After introducing the five sorting algorithms, we will summarize these methods and connect them with the java API. In addition, in order to facilitate our implementation of these sorting methods, we now use some auxiliary methods. These auxiliary methods are very simple, and their purpose is to make our code concise.

    /**
     * 比较两个大小不同的数字，如果第一个参数比较小则返回true。
     * 
     * @param v 第一个数字
     * @param w 第二个数字
     * @return 返回比较结果
     */
    public static boolean less(int v , int w){        if(v<w) return true;        return false;
    }    /**
     * 交换数组中两个索引的内容
     * 
     * @param arr 数组
     * @param v 第一个索引
     * @param w 第二个索引
     */ 
    public static void exch(int[] arr,int v ,int w){        int temp=arr[v];
        arr[v]= arr[w];
        arr[w] = temp;
    }    /**
     * 打印数组
     * 
     * @param arr 要显示的数组
     */
    public static void show(int[] arr){        for(int i=0;i<arr.length;i++)
        System.out.println(arr[i]);
    }

(2) Sorting cost model

In Java, the vast majority of elements are objects, and the description of the primary keys of these objects is through the Comparable mechanism To achieve this, Comparable has the concept of order and sorting. So how to study whether a sorting method is fast or slow, how fast it is, and how efficient it is? We will study the cost of each sorting algorithm from the following aspects.

1. Comparison and exchange (We need to calculate the number of comparisons and exchanges to judge the cost of sorting)

2. Time (The time it takes a sorting algorithm, or the time it takes in a certain situation)

3. Additional memory usage( Some sorting methods require additional memory space, while others do not)

We will give special cost estimation methods for some special sorting algorithms, For most sorting methods, we will discuss at the end when this method is suitable - after all, those useless sortings have long been eliminated.

(3) Selection sorting

Selection sorting is the simplest sorting algorithm among all sortings. The core idea of ​​selection sorting is:

Maintain an ordered subarray at the front end of the array, find the smallest element in the second half of the unordered array each time, and combine it with the first element after the end of the front end Swap an unordered element to make this element ordered. Sorting is completed when the sorted partial array elements equal the total number of elements.

In layman's terms, we first find the smallest element in the array and exchange it with the first element. If the first element is the smallest element, then it and it Swap yourself. Then we find the smallest element from the second element to the end, exchange it with the second element of the array, and so on, continuously selecting the smallest element among the remaining elements.

1. Comparison and exchange

Selection sorting has a fixed number of comparisonsN²/2, and a fixed Number of exchanges N.

In terms of the number of comparisons, selection sorting needs to compare from the first element to the last element for the first time to know what the smallest element is. In the second time, N-1 comparisons are required to know the smallest element. A total of N+(N-1)+(N-2)+ ··· + 1 = N²/2 times is required.

Because due to the programming reasons of the algorithm, even if the smallest element is already in the correct position, we still need to exchange its position with itself, so the number of exchanges is also fixed at N times.

2. Time

The running time of selection sort is fixed, which is about N²/2 times of comparison (N## In the case of #2^{/2, we can basically ignore the N times of exchange). If we cannot estimate the running time of a sorting method, we now know at least one guaranteed sorting method. As long as your sorting method is used properly, its running time will never exceed N}2^{/Time for 2 comparisons.}

3.java实现

package Sort;/**
 * 
 * @author QuinnNorris 选择排序
 */public class Sort1 {

    /**
     * @param args
     */
    public static void main(String[] args) {        // TODO Auto-generated method stub

        int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };        // 测试数组
        sort(arr);        // 调用排序算法
        Tool.show(arr);        // 打印
    }    /**
     * 用选择排序将arr升序排列
     * 
     * @param arr
     *            所要排列的数组
     */
    public static void sort(int[] arr) {        
    for (int i = 0; i < arr.length; i++) {            
    int min = i;            
    for (int j = i + 1; j < arr.length; j++)                
    if (Tool.less(arr[j], arr[min]))
                    min = j;
            Tool.exch(arr, min, i);
        }
    }
}

4.特点

选择排序非常简单，他有两个很鲜明的特点：
1.运行时间和输入无关
运行时间和输入无关，好听的讲就是无论多么乱的数据都会在固定的时间之内完成排序，但是更多的情况下，这种前一遍比较不能为后一遍比较提供任何价值的算法是非常费时的。夸张的讲，如果我们要完成某个几乎接近有序的数组的排序，你会发现，使用选择排序所需的时间和去排序那些无序的数组竟然是完全一样的。这在很多情况下是大家不能接受的。
2.数据移动最少
为了保证最少的交换数据，我们不断的进行比较，每次的交换都会百分之百的把一个数字放在正确的位置上。其他的任何排序方法都不具备这个特性。

（四）插入排序

在选择排序中，一个几乎有序的数组和一个完全无序的数组所需时间是一样的。插入排序则完美的解决了这个问题：

从数组的头部开始，通过不断的一次一位的比较和交换，让每个数据都能插入前端有序部分中自己合理的位置，当所有的元素都完成一遍操作后，排序完成。

我们将要排序的那个元素和前面一位元素比较，如果比前面的元素小，则交换位置，这个元素继续和再前面的元素比较，如果仍然小则继续交换，知道前面的元素小于该元素位置。这个时候，这个不断交换的元素就在这个数组中达到了自己合适的位置，刚才其他被交换的元素，都像是“向后移动一个位置”，为这个元素挪出了空间，这就是插入排序。这种排序很类似我们在打桥牌时整理牌的方法，不断地将牌按照大小从后向前插入。

1.比较和交换

在一个随机排序而且主键不重复的数组中，平均情况下插入排序需要N²/4次比较以及N²/4次交换。在最坏的情况下需要N²/2次比较和N²/2次交换，最好情况下需要N-1次比较和0次交换。
这个平均情况是怎么计算得出的呢？通常情况下，我们认为数组中的一个数字在整个数组中会被移动半个数组的长度（在平均情况下，每个数字都会移动到有序部分的中间位置，在这种情况下，数字自己的移动和被向后“推”的移动加起来长度为半个数组），在半个数组的移动算作平均情况下，我们得到N²/4的比较和交换次数。

2.时间

我们可以看出，用插入排序算法排序的时间和这个数组情况有很大关系，如果数组是非常无序的，它的速度要慢于选择排序，但是如果我们现在要排序的数组是几乎完全有序的，那么它的时间将会非常的小。就像我们手中握着一副全都排好顺序的扑克牌，这时你抽到一张梅花9，你可以非常快的将它插到你的手牌中。

1. 数组中每个元素距离他的最终位置不远

2. 一个有序数组的大数组接一个小数组

3. 数组中只有几个元素的位置不正确

上述的三种情况下，使用插入算法会非常非常有效。事实上，当顺序错误的数量很少的时候，插入排序会比其他任何排序算法都快。

3.java实现

package Sort;/**
 * 
 * @author QuinnNorris 插入排序
 */public class Sort2 {

    /**
     * @param args
     */
    public static void main(String[] args) {        // TODO Auto-generated method stub

        int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };        // 测试数组
        sort(arr);        // 调用排序算法
        Tool.show(arr);        // 打印
    }    /**
     * 用插入排序将arr升序排列
     * 
     * @param arr
     *            所要排列的数组
     */
    public static void sort(int[] arr) {        
    for (int i = 0; i < arr.length; i++)            
    for (int j = i; j > 0; j--)                
    if (Tool.less(arr[j], arr[j - 1]))
                    Tool.exch(arr, j, j - 1);
    }
}

4.特点

在插入排序中，因为他的速度和原有的序列有很大关系。在这里，我们将在原序列中位置顺序颠倒的一对数字叫做倒置，这只是我们起的一个名字，它表示两个数字的位置是错误的（a应该在b的前面，但是在数组中a在b的后面，无论a与b相隔多远，都可以称a、b是一个倒置）。插入排序具有以下几点特性：

1. 交换和比较的次数相同

2. 比较的次数大于等于倒置的数量

3. 比较的次数小于等于倒置数量加上数组的大小再减一

除此之外，插入排序作为一种初级排序算法，会在之后的高级排序算法中作为一个中间算法频频出现，我们会在以后再见到他。

（五）选择算法和插入算法比较

这两种算法是如此的相似，以至于我们非常好奇想将他们比较一番。对于随机排序无重复的数组，插入排序和选择排序的运行时间都是平方级别的，所以两者只比应该是一个较小的常数。

(6) Hill Sorting

The sorting algorithm we are going to introduce next is not a primary sorting algorithm, but it actually uses the technology of the insertion algorithm. We might as well discuss it here. Hill sorting means:

By formulating a constant h value from large to small, and inserting sorting, the elements with any interval of h in the array are ordered. Keep reducing the size of h until h=1, so that the entire array is ordered.

We still use bridge as an analogy. At the beginning, you have a deck of cards in no order. You can find the positions one by one, but then you suddenly feel that this method It’s too slow, so you plan to do a rough screening first. You put some cards in order, but other cards are not in order. In this way, you sift through your cards several times and finally make all the cards in your hand in order. This is Hill sort.

When we need to sort tens of thousands of arrays, we can usually use Hill sorting.
In Hill sorting, we first define an h. We use h as the interval to divide a subarray. We use the insertion algorithm to sort this subarray. Then we continue to make h smaller, and we sort the new array. Finally, when h is 1, this sorting keeps all the data in order.

1. Advantages

So what are the advantages of Hill sorting? We know that the advantage of insertion sort is that it is extremely fast for sorting partially ordered sequences, and it is very fast for sorting small arrays. Our Hill sorting combines these two advantages. When h is large, the entire array is relatively small, and insertion sort is faster. When h is small, the entire array has gradually become more orderly. At this time, using insertion sort is also a very good choice. It can be said that Hill sorting combines these two advantages, and the overall time is relatively fast.

2. Time

For Hill sorting, we do not intend to analyze it according to our above analysis method for the following reasons. First of all, Hill sorting is very difficult to study exchange and comparison, because the key factor is h, h is a constant, and we can change the interval of this jump by setting different h. And there is no clear explanation: what rule does h follow to achieve the best effect (usually we can use 3*h+1, that is: 1, 4, 13, 40, 121, 364...this group of numbers as h). Since h cannot be determined, there is no optimal time.

3. Practical application

Experienced programmers sometimes use Hill sorting, because for medium-sized arrays, the running time of Hill sorting is acceptable. The amount of code is very small and no additional memory space is used. Maybe we do have faster algorithms but for large N, they are probably only less than twice as fast as Hill sort. And it's very complicated. If you need to sort but don't have a systematic sorting function, you may consider using Hill sorting, and then consider whether to replace it with a more advanced sorting method.

Program = data structure + algorithm. For those frameworks that build projects that are not written by us, what can really judge the level of a project is whether the data structures we customize are convenient, concise, and low-coupled; whether the algorithms we use to implement these methods are fast and effective. , less error-prone. If what you want to do is not the kind of job of moving bricks from morning to night every day, learning algorithms and analyzing data structures is definitely the only way for you to increase your level.

The above is the content of java algorithm (1) - primary sorting algorithm. For more related content, please pay attention to the PHP Chinese website (www.php.cn)!