Sorting algorithm summary

Recommended for you: Get network issues from WhatsUp Gold. Not end users.

Recently started to read the introduction to algorithms, beginning to see, for sorting algorithm before this name is not familiar with the bubble sort algorithm, the other algorithm is only heard, not in-depth study. Read the book will know there are so many algorithms, to sum up, keep the future view, first understand the principle of the algorithm, the performance efficiency, not on.

1,Insertion sort

          One has ordered sequence of data, the data sequence has been good to insert a number, but after the insertion of the data sequence is still in an orderly manner, this time it is necessary to use a new ranking method -- insertion sort, insertion sort is the basic operation of a data into ordered data already sorted, and get a new, a number plus one of the ordered data, apply a small amount of data sorting algorithms, the time complexity is O(n^2). Is the sort of stable method. Insertion algorithm to the array is divided into two parts: the first part contains all the elements of the array, but the last element except, while the second part contains only one element. In the first part, after sorting, then is the first part position in ordered this last element into at the moment.

       Simple said is like when playing poker, to draw a card, you draw second cards on the first hand of cards than you, and then inserted into a suitable position, the brand is orderly.

The specific algorithm is described as follows:

⒈ Starting with the first element, the element that is already sorted

⒉ Remove the next element, scanning from back to front in already sorted sequence of elements

⒊ If the element (sorted) is greater than the new element, the element is moved to the next location

⒋ Repeat step 3, until you find the sorted elements is less than or equal to the new location

⒌ Insert the new element to the next position

⒍ Repeat step 2

Algorithm:

int[] abs=new int[]{5,35,69,38,41,2,11,85};
        for(int i=0;i<abs.length;i++){
            int j=i;
            int temp=abs[i];
            while(j>0 && temp<abs[j-1]){
                abs[j]=abs[j-1];
                j--;
            }
            abs[j]=temp;
        }
        printf(abs);

This print out the results is the sorted sequence.

2,Bubble sort

It is a common and simple algorithm.

It repeatedly visited to sort sequence, comparison of the two elements of a sequence, if the error they put them to exchange. Visit the sequence is repeated until no longer need to exchange, which means the series has been sequenced.

Bubble sort algorithm works as follows:

  1. Comparison of adjacent elements. If the first is larger than the second, can exchange their two.

  2. For the same work for each pair of adjacent elements, starting from the first to the end of the last on. At this point, the last element should be the largest number.

  3. For all elements, repeat the above steps, except for the last one.

  4. For each of the fewer elements repeat the above steps, until no need of digital.

Algorithm:

int[] abs=new int[]{5,35,69,38,41,2,11,85};
        for(int i=0;i<abs.length;i++){
            for(int j=i;j<abs.length;j++){
                if(abs[i]>abs[j]){
                    int tmp=abs[i];
                    abs[i]=abs[j];
                    abs[j]=tmp;
                }
            }
        }

printf(abs);

3,Cocktail sort

Cocktail sort is a deformation of bubble sort, the bubble sort algorithm is different with that sort is sorted in sequence to bidirectional. An array of digital is the irregular discharge, first find the smallest number, put him in the first place, and then find the largest number in the last one. And then find the smallest number in second, and found second large numbers in the bottom second. And so on, until the completion of sequencing.

Algorithm:

for(int i = 0 ; i <src.length/2 ; i++){
            for(int j = 0 ; j <src.length-i-1 ; j++){
                if(src[j] <src[j+1]){
                    int temp = src[j];
                    src[j] = src[j+1];
                    src[j+1] = temp;
                }
            System.out.println("The exchange of small"+Arrays.toString(src));
            }
            //The maximum row to the head of line
            for(int j = src.length - i -1 ; j > i ; j--){
                if(src[j] > src[j-1]){
                    int temp = src[j];
                    src[j] = src[j-1];
                    src[j-1] = temp;
                }
            System.out.println("Exchange"+Arrays.toString(src));
            }
            System.out.println("The " +i+" scheduling results: "+Arrays.toString(src));
        }

4,Two binary sort tree

Two binary sort tree (Binary Sort Tree) is also called the two binary search tree. It is either a hollow tree; or has the following properties of two binary tree:

(1)If the left sub tree is not empty, then the left sub tree of all node values are less than the root node of its value,

(2)If the right subtree is not empty, then the right subtree all node values are greater than the value of its root node,

(3)Left, right subtree is respectively two binary sort tree.

5,Other sorting method

Sorting method also includes bucket sorting, counting sort, merge sort, pigeonhole sort, Gnome sort, library sort.

The methods are more rare, is not described in detail.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download

Posted by Cheney at November 16, 2013 - 10:47 AM