排序-插入冒泡交换选择与二分查找

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
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

/**交换T的值**/
template <typename T>
void swap(T* p, T* q)
{
    T tmp = *p;
    *p = *q;
    *q = tmp;
}

/**输出T数组中各个元素的值**/
template <typename T>
void showArray(const T* pArray,const int arrayLen)
{
    for (int i = 0; i < arrayLen; ++i) {
        printf("%d->",pArray[i]);
    }
    printf("end");
}

/**直接插入排序，时间复杂度，平方级，稳定排序**/
template <typename T>
void insertSort(T* pArray, const int arrayLen)
{
    T tmp;
    
    for (int i = 1; i < arrayLen; ++i) {
        
        tmp = pArray[i];
        int j = 0;
        
        for (j = i; j > 0; --j) {
            
            if (tmp < pArray[j - 1]) {
                pArray[j] = pArray[j - 1];
            }
            else
            {
                break;
            }
        }
        
        pArray[j] = tmp;
        
    }
}

/**冒泡排序，时间复杂度，平方级，稳定排序**/
template <typename T>
void bubbleSort(T* pArray, const int arrayLen)
{
    bool isExchanged = false;
    for (int i = arrayLen - 1; i >= 0; --i) {
        
        isExchanged = false;
        
        for (int j = 0 ; j < i; ++j) {
            if (pArray[j + 1] < pArray[j]) {
                swap(&pArray[j + 1], &pArray[j]);
                isExchanged = true;
            }
        }
        
        if (!isExchanged) {
            break;
        }
    }
}

/**交换排序**/
template <typename T>
void exchangeSort(T* pArray, const int arrayLen)
{
    for (int i = 0; i < arrayLen; ++i) {
        
        for (int j = i + 1; j < arrayLen; ++j) {
            
            if (pArray[j] < pArray[i]) {
                swap(&pArray[j], &pArray[i]);
            }
            
        }
        
    }
}

/**选择排序**/
template <typename T>
void selectSort(T* pArray, const int arrayLen)
{
    int smallIndex = 0;
    
    for (int i = 0; i < arrayLen; ++i) {
        
        smallIndex = i;
        
        for (int j = i + 1; j < arrayLen; ++j) {
            if (pArray[smallIndex] > pArray[j]) {
                smallIndex = j;
            }
        }
        
        if (i != smallIndex) {
            swap(&pArray[i], &pArray[smallIndex]);
        }
        
    }
}

template <typename T>
const int binaryFind(const T* pArray, const int arrayLen,const T value)
{
    int mid = 0;
    int low = 0;
    int high = arrayLen - 1;
    
    while (low <= high) {
        mid = low + (high - low)/2;
        
        if (pArray[mid] > value)
        {
            high = mid - 1;
        }
        else if (pArray[mid] < value)
        {
            low = mid + 1;
        }
        else if (pArray[mid] == value) {
            return mid;
        }
    }
    
    return -1;
}

调用CODE如下：
- (void)viewDidLoad
{
    [super viewDidLoad];
// Do any additional setup after loading the view, typically from a nib.
    
    const int  KArrayLength = 10;
    int  pArray[KArrayLength] = {22,34,89,0,3,81,99,23,1,10} ;
   
    showArray(pArray, KArrayLength);
    //insertSort(pArray, KArrayLength);
    //bubbleSort(pArray, KArrayLength);
    //selectSort(pArray, KArrayLength);
    exchangeSort(pArray, KArrayLength);
    printf("\n");
    showArray(pArray, KArrayLength);

    int index = binaryFind(pArray, KArrayLength, 81);
    printf("\nindex = %d\n",index);
    
    index = binaryFind(pArray, KArrayLength, 811);
    printf("index = %d",index);
}