Sorting algorithm display

Sorting Definition and Its Properties

1. Bubble Sorting

Bubble Sort is a sort of computer science Simpler in the field Sorting algorithm.

_It repeatedly visits the column of elements to be sorted, compares two adjacent elements in turn, and swaps them if the order (large to small, Z to A) is wrong.The work of visiting an element is repeated until no adjacent elements need to be exchanged, that is, the element column has been sorted.

_The algorithm's name comes from the fact that smaller elements "float" slowly to the top of a number of columns (ascending or descending) by exchange, just as the bubbles of carbon dioxide in a carbonated drink eventually float to the top, hence the name "bubble sort".

2. Select Sort

Selection sort is a simple and intuitive method Sorting algorithm .It works like this: the first time it's sorted data elements Select the smallest (or largest) element, store it at the beginning of the sequence, find the smallest (largest) element from the remaining unsorted elements, and place it at the end of the sorted sequence.And so on until all the data elements to be sorted have zero number.Selective sorting is an unstable sorting method.

3. Insert Sorting

Insertion sort is simple, intuitive and stable Sorting algorithm .If you have an already ordered data sequence, you need to insert a number into the already ordered data sequence, but you want the data sequence to be ordered after insertion, then you need a new sort method-- Insert Sorting The algorithm is suitable for sorting a small amount of data. Time Complexity O(n^2).Is a stable sorting method.The insertion algorithm sorts the array It is divided into two parts: the first part contains all the elements of the array except the last one, which gives the array one more space to insert, and the second part contains only one element, which is the element to insert.After sorting the first part, insert the last element into the sorted first part.

4. Merge and Sort

Merge sorting (MERGE-SORT) is an effective sorting algorithm based on merge operation. It is a very typical application of Divide and Conquer.Merge the existing ordered subsequences to obtain a completely ordered sequence; that is, order each subsequence before ordering subsequence segments.If two ordered tables are merged into one ordered table, it is called two-way Merger .Merge sort is a stable sort method.

5. Quick Sorting

Quicksort is an improvement on bubble sorting.

_Quick sorting was proposed by C. A. R. Hoare in 1960.The basic idea is that the data to be sorted is divided into two separate parts by one-time sorting, in which all the data in one part is smaller than all the data in the other part, and then sorted separately by this method. The whole sorting process can be recursion Proceed so that the entire data becomes ordered sequence

Sorting algorithm Title example:

75. Color Classification

1. Bubble sort

	void sortColors(vector<int>& nums) {
		for (int i = 0; i < nums.size()-1; i++) {
			for (int j = 0; j < nums.size()-i-1; j++) {
				if (nums[j] > nums[j+1]) {
					int temp = nums[j];
					nums[j] = nums[j+1];
					nums[j+1] = temp;
				}
				
			}
		}
	
	}

2. Select Sort

	void sortColors(vector<int>& nums) {
		for (int i = 0; i < nums.size(); i++) {
			int min = i;
			for (int j = i+1; j < nums.size(); j++) {
				if (nums[min] > nums[j]) {
					min = j;
				}

			}
			if (min != i) {
				int temp = nums[i];
				nums[i] = nums[min];
				nums[min] = temp;
			}
		}
	
	}

3. Triple insertion sort

public void sortColors(int[] nums) {
        int zero = -1; //nums[0......zero] =0
        int two = nums.length; //nums[two......n) =0

        for(int i = 0;i < two;){
            if(nums[i] == 1){
                i++;
            }else if(nums[i] == 2){
                swap(nums,i,--two);
            }else{
                swap(nums,i++,++zero);
            }
        }
    }
      public void swap(int nums[],int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }

88. Merge two ordered arrays

1. Two Way Merge Method

 public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] newNums = new int[m+n];
        int i=0,j=0,k=0;
        while (i<m&&j<n) {
            newNums[k++] = nums1[i] < nums2[j] ? nums1[i++] : nums2[j++];
        }
        while (i < m){
            newNums[k++] = nums1[i++];
        }
        while (j < n) {
            newNums[k++] = nums2[j++];
        }

        for(int l =0;l< newNums.length;l++){
            nums1[l] = newNums[l];
            System.out.print(nums1[l]+" ");
        }
    }

215. The K largest element in the array

1. Optimized Bubble Method Edition

 public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        int kk = nums.length - k;
        do{
            int index = 0;//Sort auxiliary coordinate points in nums(index...n) is ordered
            for (int i = 0; i < nums.length - 1; i++) {
                if (nums[i] > nums[i + 1]) {
                    int temp = nums[i];
                    nums[i] = nums[i + 1];
                    nums[i + 1] = temp;

                    index = i;//Record the coordinates of the last exchange
                }
            }
            n = index;
            if (index < kk) return nums[kk];
        }while(n > 0);
        return nums[kk];
    }

2. Quick Sorting

    public int findKthLargest2(int[] nums, int k) {

        return 0;
    }

Posted on Mon, 16 Mar 2020 10:21:59 -0700 by markjohnson