Data structure: binary search, quick sorting ideas and implementation

Recently, I have been thinking about how to design, how to code better, and more fully understand the object-oriented thinking, and I also deliberately study in this aspect. After writing code for several years, I also summarized and summarized it. I found that the most important thing is to think about it. I reviewed the book "Programming Practice" and further standardized and reflected on the style, quality, performance, portability, etc. of the code I wrote. The knowledge and algorithms of data structures will be further consolidated. Let’s write about algorithms that are often encountered in written exams: binary search, quick sort algorithm. The key to implementing an algorithm lies in the idea of ​​implementation.

(1) Binary search
Binary search is actually a half search, a more efficient search method. Search for required arrays.
The main idea is: (Suppose the searched array period is array[low, high])
(1) Determine the middle position K of the period
(2) Compare the searched value T with array[k]. If they are equal, the search succeeds and returns to this position; otherwise, determine the new search area and continue the binary search. The area is determined as follows:
a.array[k]>T From the orderliness of the array, it can be known that array[k,k+1,...,high]>T; so the new interval is array[low,..., K-1]
b.array[k]Target array (already sorted)

/// Number to be searched for

/// Target number Index

               while (low <= low = mid + 1;

                                                                                                                                                                                                                                                                 Since {H high = mid -1;
}
else
{
return mid;
}}
Return -1;
}

(2) Quick sorting algorithm
is an excellent excellent example of avoiding additional calculations. The way it works is to divide the array into small and large elements. The basic idea is:
Take an element from the array as the base value.
Divide the other elements into two groups:
"Small" are those that are smaller than the base value. element.
"Big" are those elements that are larger than the base value,
Recursively sort these two groups.
The reason why quick sort is fast is that once it knows that an element is smaller than the baseline value, it does not need to compare with those larger elements. Large elements do not need to be compared with small elements. This property makes quick sort much faster than simple sorting and bubble sorting.

时间复杂度：O（nlogn）
代码实现：
        ///

        /// 快速排序
        ///

        ///
        ///
        ///
        public void QuickSort(int[] array,int left,int right)
        {
            int last;
            if (left>=right)
                return;
            int rand = (left+right)/2;
            Swap(array, left, rand);
            last = left;
            for (int i = left + 1; i <= right; i++)
            {
                if (array[i] < array[left])
                    Swap(array, ++last, i);
            }
            Swap(array, left, last);
            QuickSort(array, left, last - 1);
            QuickSort(array, last + 1, right);
        }

        ///

        /// 交换两个值
        ///

        ///
        ///
        ///
        private void Swap(int[] a,int i,int j)
        {
            int temp;
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }

更多数据结构之二分法查找、快速排序思想与实现相关文章请关注PHP中文网！