C++ 一些基本算法练习

时间：2014-01-24 04:46:41 收藏：0 阅读：496
以体会思想为目的，进行c++算法基本练习。
涉及二分法，迭代器移动，快排。
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include <iostream>
#include <string>
using 
namespace 
std;
/*
二分法找元素，核心思想是二分判断
*/
int 
find_element_in_array(int 
*a,int 
length,int 
element)
{
    int 
begin, end, mid;
    begin = 0;
    end = length-1;
    mid = (end + begin) / 2;
    while 
(begin < end && a[mid] != element)
    {   
        if 
(a[mid] > element)
        {
            //cout <<a[mid]<< endl;
            end = mid-1;
        }
        if 
(a[mid] < element)
        {
            //cout << a[mid] << endl;
            begin = mid+1;  
        }
        mid = (end + begin) / 2;
    }
    if 
(element == a[mid])
    {
        cout << "element : " 
<< element << " a[mid] : " 
<< a[mid] << endl;
    }
    else
    {
        cout << "not found " 
<< element<<endl;
    }
    return 
0;
}
void 
main_find_element_in_array()
{
    int 
array1[10] = { 1, 5, 23, 33, 45, 57, 59, 76, 87, 93 };
    find_element_in_array(array1, 10, 59);
}
/*
第一种，以空间换时间，开辟一个新空间，利用尾迭代器递减，遍历一次size（）
*/
void 
string_reverse_one(const 
string str)
{
    string temp="";
    auto 
end = str.cend();
    for 
(auto 
s : str)
    {
        temp += *(--end);
    }
    cout << temp << endl;
}
void 
main_string_reverse_one()
{
    string s = "my name is kobe";
    string_reverse_one(s);
}
/*
第二种，字符串翻转的核显思想是，利用迭代器，通过交换头尾迭代器的值，这样只需遍历size（）/2
*/
void 
string_reverse_two(string &str)
{
    auto 
begin = str.begin();
    auto 
end = str.end() - 1;
    if 
(str.size() % 2 != 0)
    {
        while 
(begin != end)
        {
            auto 
t = *end;
            *end = *begin;
            *begin = t;
            begin++;
            end--;
        }
    }
    if 
(str.size() % 2 == 0)
    {   
        int 
cout = 0;
        while 
(cout != (str.size()/2))
        {
            auto 
t = *end;
            *end = *begin;
            *begin = t;
            begin++;
            end--;
            cout++;
        }
    }
}
void 
main_string_reverse_two()
{
    string s = "my name is kobe!";
    string_reverse_two(s);
    cout << s << endl;
}
 
 
/*
快排的核心思想是，找到当前列表的第一个元素应该在的位置！
然后递归剩下位置的数据
*/
void 
swap(int 
*a, int 
low, int 
high)
{
    int 
temp;
    temp = a[low];
    a[low] = a[high];
    a[high] = temp;
}
int 
Partition(int 
*a, int 
low, int 
high)
{
    int 
pivotkey = a[low];
    while 
(low < high)
    {
        while 
(low < high && a[high] >= pivotkey)
            high--;
        swap(a, low, high);
        while 
(low < high && a[low] <= pivotkey)
            low++;
        swap(a, low, high);
    }
    return 
low;
}
void 
Qsort(int 
*a, int 
low, int 
high)
{
    int 
pivot;
    if 
(low < high)
    {
        pivot = Partition(a, low, high);
        Qsort(a, low, pivot-1);
        Qsort(a, pivot+1, high);
    }
}
void 
quick_sort(int 
*a, int 
length)
{
    length = length - 1;
    Qsort(a, 0, length);
}
void 
main_quick_sort()
{
    int 
array1[10] = { 12, 5, 53, 83, 45, 7, 69, 56, 87, 93 };
    quick_sort(array1,10);
    for 
(int 
i : array1)
    {
        if 
(i!=0)
            cout << i << ‘ ‘;
    }
}
 
 
void 
main()
{   
    cout << "二分法查找" 
<< endl;
    main_find_element_in_array();
    cout << "翻转字符串方法1" 
<< endl;
    main_string_reverse_one();
    cout << "翻转字符串方法2" 
<< endl;
    main_string_reverse_two();
    cout << "快排排序" 
<< endl;
    main_quick_sort();
}
原文：http://www.cnblogs.com/wk23/p/3531474.html