Selection sort is that simple

From the last article has explained the bubble sort, this chapter mainly explains the selection sort, I hope you can understand and handwritten selection sort code, and then pass the interview! Please point out in the comments if I have made any mistakes.

Selection sort introduction and stability description

Source BCO:

Selection sort is a simple and intuitive sorting algorithm. It works by selecting the smallest (or largest) element from the data elements to be sorted and storing it at the beginning (end) of the sequence until all the data elements to be sorted are sorted. Selection sorting is an unstable sorting method (for example, sequence [5, 5, 3] swaps the first [5] with [3] on its first attempt, causing the first 5 to move behind the second 5).

The above mentioned selection sort is unstable sorting method, so our bubble sort is not stable sorting method? What do I mean by stable?

To judge whether a certain sorting algorithm is stable or not, we can simply understand it as: the position sequence of the two equal numbers before and after sorting is the same as that of the two numbers after sorting

  • If they are the same, it is a stable sorting method.
  • If not, it is an unstable sorting method

If the array before the sort is [3,3,1], the result after the first sort is [1,3,3], assuming we use selective sort. This array has two identical values in array[0] and array[1]. The result is sorted so that array[0] runs on array[2].

So this leads to two equal numbers that are not in the same order before and after the sequence as they are after the sequence, so we say it’s unstable

Going back to the above problem, bubble sort is stable mainly because there is no interchange of equal data when two pairs are compared (because there is no need). So it doesn’t have two equal numbers that are not in the same order before and after the sequence as they are after the sequence.

So what’s the advantage of stable sorting?

  • Refer to Zhihu Answer @Lone Ranger’s answer:

If we sort only a string of numbers, then stability really doesn’t matter, because the property of a string of numbers is a single one, the size of the number. However, sorting elements often have more than one attribute. For example, we sort a group of people by age, but people also have height and weight attributes in addition to age attributes. If we do not want to destroy the original height and weight order at the same age, we must use stable sorting algorithm.

It is clear that stability makes sense only if you do not want to destroy the original order in “quadratic” sorting

References:

  • www.zhihu.com/question/46…
  • tieba.baidu.com/p/872860935
  • www.cnblogs.com/codingmylif…

One, the first sequence

It works by selecting the smallest (or largest) element from the data elements to be sorted and storing it at the beginning (end) of the sequence until all the data elements to be sorted are sorted

First, we create the array and find its maximum value (this is easy):



    int[] arrays = {2.3.1.4.3.5.1.6.1.2.3.7.2.3};

    // Assume Max is maximum
    int max = 0;


    for (int i = 0; i < arrays.length; i++) {
        if(arrays[i] > max) { max = arrays[i]; }}Copy the code

The largest number is then swapped with the number at the end of the array:


	// Use temporary variables to make the two numbers interchangeable
	int temp;
	temp = arrays[11];
	arrays[11] = arrays[13];
	arrays[13] = temp;

Copy the code

So after the first sort, we’re at the end of the array.

Second, the second order

Get the largest number from the array again (other than the one already sorted) :


    int max2 = 0;
    for (int i = 0; i < (arrays.length - 1); i++) {
        if (arrays[i] > max2) {
            max2 = arrays[i];
        }
    }

    System.out.println(max2);

Copy the code

Swap the maximum value with the penultimate value of the array:


    temp = arrays[7];
    arrays[7] = arrays[12];
    arrays[12] = temp;

Copy the code

After the second sort, we can sort up to two numbers in the array

Iii. Code simplification

In fact, we can feel the pattern of the first two sorts:

  • An array is neededn-1Sort (because there is no need to find the maximum until there is one element left)
  • Every time I swap, I reduce the range by 1 when I find the maximum again
  • Query the current maximum number of runs actually do not need to know what the maximum value is (above I find the maximum value, I have to manually count its horn), know its array horn can be, swap is also based on the horn to swap

First run: iterate through the group of 14 numbers to get the maximum value, and place it to the end of the array [13] Second run: iterate through the group of 13 numbers to get the maximum value, and place it to the second to last of the array [12]

.

The array has 14 numbers, and it takes 13 sorts.



    // Record the maximum number of runs
    int pos ;

    // Swap variables
    int temp;


    // The outer loop controls the number of runs to be sorted
    for (int i = 0; i < arrays.length - 1; i++) {

        // New number of runs, reassign the corner label to 0
        pos = 0;

        // The inner loop controls the number of numbers traversed and obtains the largest number of horn markers
        for (int j = 0; j < arrays.length - i; j++) {
            
            if(arrays[j] > arrays[pos]) { pos = j; }}/ / exchange
        temp = arrays[pos];
        arrays[pos] = arrays[arrays.length - 1 - i];
        arrays[arrays.length - 1 - i] = temp;


    }

    System.out.println("Java3y" + arrays);
Copy the code

Fourth, selection sorting optimization

The blogger has not yet thought of a better optimization method, if the students who read this article know of a better optimization method or code can be written better, welcome to leave a message in the comments!

Select sort optimization method, feel the selection sort changed a taste, you can also go to see:

  • It takes the maximum and the minimum at the same time, and inserts them into the top and bottom of the array respectively.
  • www.cnblogs.com/TangMoon/p/…

5. Read more

C language implementation

          int findMaxPos ( int arr[], int n)
        {
            int max = arr[0];
            int pos = 0; 
            for (int i = 1; i < n; i++) {
                if(arr[i] > max) { max = arr[i]; pos = i; }}return pos;
        }

        void selectionSort ( int arr[], int n)
        {
            while (n > 1) 
            {
                int pos = findMaxPos(arr, n);
                int temp = arr[pos];
                arr[pos] = arr[n - 1];
                arr[n - 1] = temp;
                n--;//}}int main (a)
        {
            int arr[] = {5.32.7.89.2.3.4.8.9};
            selectionSort(arr, 9);
            for (int i = 0; i < 9; i++)
                cout << arr[i] << endl;
        }

Copy the code

If the article has the wrong place welcome to correct, everybody exchanges with each other. Students who are used to reading technical articles on wechat and want to get more Java resources can follow the wechat public account :Java3y